This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
For calculating the exponential cycles, is there any way to do without computer
Log in to reply
I didn't use a computer to do this one, I just did pencil and paper. It's only a handful of operations, and they're not very big, especially if you take advantage of modular arithmetic properties, as well as Euler's theorem (The period for 2 3 x modulo 2 9 must divide ϕ ( 2 9 ) = 2 8 ):
2 3 ≡ − 6 mod 2 9 → 2 3 2 ≡ 3 6 ≡ 7 mod 2 9
2 3 4 ≡ ( 2 3 2 ) 2 ≡ 4 9 ≡ 2 0 mod 2 9
2 3 7 ≡ 2 3 4 ⋅ 2 3 2 ⋅ 2 3 ≡ 2 0 ⋅ 7 ⋅ 2 3 ≡ ( − 9 ) ⋅ 7 ⋅ ( − 6 )
. . . ≡ 5 4 ⋅ 7 ≡ ( − 4 ) ⋅ 7 ≡ − 2 8 ≡ 1 mod 2 9
Doing multiplication modulo 7 , 3 , and 2 is a cakewalk.
We need to figure out exponentiation cycles to solve this problem. Observe, for example, consecutive powers of 2 3 modulo 2 9 :
{ 2 3 0 , 2 3 1 , 2 3 2 , . . . } ≡ { 1 , 2 3 , 7 , 1 6 , 2 0 , 2 5 , 2 4 , 1 , 2 3 , 7 , 1 6 , . . . } mod 2 9
The powers repeat every 7 elements. So, if we can compute 2 2 2 3 modulo 7 , we can get the answer.
Recursing on down, we find we need to compute 2 1 2 3 modulo 3 , and 2 0 2 3 modulo 2 . That last term is just 1 X modulo 2 , for some positively enormous X , so we know it evaluates to 1 modulo 2 .
Plugging this result backwards, we get 2 1 2 3 ≡ 2 modulo 3 , 2 2 2 3 ≡ 4 modulo 7 , and finally, 2 3 2 3 ≡ 2 0 modulo 2 9 for a final answer of 2 0