Question

How do you reduce mod (133) starting with 1 by applying g, f, f, f, f, g, f, g with a = 2 to get 1, 2, 4, 16, - 10, -33, 50, -27, -5...thus showing 2¹³³ = (is congruent to) -5 but is not congruent to 2 mod (133).

I am stuck on how to apply the fs and gs to get 1, 2, 4, 16, -10, -33, 50, -27, -5....please show me how to get each of those numbers.  

Answer 1

$2^{0}\equiv 1 \ mod\ 133$

$2^{1}\equiv 2 \ mod\ 133$

$2^{2}\equiv (2\times2) \ mod\ 133=4 \ mod \ 133$

$2^{4}\equiv (4\times4) \ mod\ 133=16 \ mod \ 133$$2^{8}=2^{4}\times \2^{4}\equiv (16\times16) \ mod\ 133=256\ mod\ 133$    =(256-133-133) mod 133= -10 mod 133

$2^{16}=2^{8}\times \2^{8}\equiv (-10\times-10) \ mod\ 133=100\ mod\ 133$

=(100-133) mod 133= -33 mod 133

$2^{32}=2^{16}\times \2^{16}\equiv (-33\times-33) \ mod\ 133=1089\ mod\ 133$ =(1089-133×8) mod 133=25 mod 133

$2^{64}=2^{32}\times \2^{32}\equiv (25\times25) \ mod\ 133=625\ mod\ 133$

=(625-133×4) mod 133=93 mod 133

= -40 mod 133

$2^{128}=2^{64}\times \2^{64}\equiv (-40\times -40) \ mod\ 133=1600\ mod\ 133$

=(1600-133×12) mod 133=4 mod 133

$2^{133}=2^{128}\times \2^{4} \times 2\equiv (4\times 16 \times 2) \ mod\ 133=128\ mod\ 133$ =(128-133) mod 133= -5 mod 133