Cycle Length of the Positive Powers of Two Mod Powers of Tenby DoctorBinary Tags: group theory, modular arithmetic, period, residue class 

#1
Oct1909, 11:35 AM

P: 43

The positive powers of 2 mod 5^m cycle with period 4*5^(m1), which you can prove by showing that 2 is a primitive root mod powers of 5. I want to prove that the positive powers of two, mod 10^m, also cycle with this same period. How do I go from this powers of 5 result to powers of 10?
The Chinese Remainder Theorem (CRT) obviously came to mind, so I considered the powers of 2 mod 2^m. Starting at 2^m, they cycle with period 1 (they are always 0). The answer, I'm sure you're going to say, is to multiply the two periods: 1 x 4 = 4. But what specifically about the CRT lets me do that? The statements of the CRT I've seen talk about the residues, not the periods. Maybe I need to invoke an underlying theorem from group theory instead? Thanks. 



#2
Oct2109, 11:28 AM

P: 43





#3
Oct2209, 04:12 AM

P: 986

Periodicity implies that there's i0 such that, for all i>=i0, 2^(i+p) = 2^i mod 5^m,
therefore 2^(i+p) = 2^i + n*5^m. It's easy to see that n = n' * 2^i0. If i0 >= m, 2^(i+p) = 2^i + n' * 10^m, which proves that your original period mod 5^m is also a period mod 10^m. On the other hand, any period mod 10^m must be a period mod 5^m: 2^(i+p) = n * 10^m + 2^i = (n*2^m)*5^m + 2^i Which proves that two periods are equal. 



#4
Oct2309, 10:52 AM

P: 43

Cycle Length of the Positive Powers of Two Mod Powers of Ten
Nice approach (I guess in a way it's using the CRT implicitly). Thanks.
I have two questions though: 1) Isn't i0 = m? 2) 



#5
Oct2309, 04:47 PM

P: 986

1) Maybe, I wasn't trying to prove that.
2) 2^(i+p) = 2^i + n*5^m, therefore 2^i * (2^p  1) = n*5^m, RHS is divisible by 2^i. 



#6
Oct2609, 10:49 AM

P: 43





#7
Oct2609, 12:38 PM

P: 986

i0 has to be m or greater.
If p is the smallest period mod 5^m and we can prove that it is also a period mod 10^m, it's still possible that p is the multiple of the smallest period mod 10^m. 



#8
Oct2609, 01:01 PM

P: 43

OK, I get it now. The issue is that 10^m's period COULD be less than 5^m's period. The second part of your proof shows it's not.
As for i0, I would still say it's m because your statement "for all i>=i0" itself implies m or greater. I REALLY appreciate the help! 



#9
Nov909, 10:59 AM

P: 43

I wrote this proof up in detail here: http://www.exploringbinary.com/cycle...powersoften/ .



Register to reply 
Related Discussions  
sum of the fourth powers of the first n positive integers  Calculus & Beyond Homework  1  
powers  Introductory Physics Homework  7  
Powers of Ten  General Discussion  3  
never done logarithms  General Math  5  
Powers of Ten  Biology  5 