Register to reply

Cycle Length of the Positive Powers of Two Mod Powers of Ten

Share this thread:
DoctorBinary
#1
Oct19-09, 11:35 AM
P: 43
The positive powers of 2 mod 5^m cycle with period 4*5^(m-1), 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.
Phys.Org News Partner Science news on Phys.org
What lit up the universe?
Sheepdogs use just two simple rules to round up large herds of sheep
Animals first flex their muscles
DoctorBinary
#2
Oct21-09, 11:28 AM
P: 43
Quote Quote by DoctorBinary View Post
... is to multiply the two periods: 1 x 4 = 4.
That was an example for m=1. I should have said, 1 x 4*5^(m-1).
hamster143
#3
Oct22-09, 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.

DoctorBinary
#4
Oct23-09, 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)
Quote Quote by hamster143 View Post
It's easy to see that n = n' * 2^i0
I see it in examples, but not algebraically. Could you elaborate?
hamster143
#5
Oct23-09, 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.
DoctorBinary
#6
Oct26-09, 10:49 AM
P: 43
Quote Quote by hamster143 View Post
1) Maybe, I wasn't trying to prove that.
I think i0 HAS to be m in order for it to work (to get the 2^m you need to match the 5^m).

Quote Quote by hamster143 View Post
On the other hand, any period mod 10^m must be a period mod 5^m
I was wondering -- is this direction necessary? Isn't showing that the period mod 5^m is the period mod 10^m sufficient? How could there be more than one period for the powers of two mod 10^m (for any m)?
hamster143
#7
Oct26-09, 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.
DoctorBinary
#8
Oct26-09, 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!
DoctorBinary
#9
Nov9-09, 10:59 AM
P: 43
I wrote this proof up in detail here: http://www.exploringbinary.com/cycle...powers-of-ten/ .


Register to reply

Related Discussions
Sum of the fourth powers of the first n positive integers Calculus & Beyond Homework 1
How to write this logarithmic equation as a power Introductory Physics Homework 7
Powers of Ten General Discussion 3
Never done logarithms General Math 5
Powers of Ten Biology 5