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


by DoctorBinary
Tags: group theory, modular arithmetic, period, residue class
DoctorBinary
DoctorBinary is offline
#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
Going nuts? Turkey looks to pistachios to heat new eco-city
Space-tested fluid flow concept advances infectious disease diagnoses
SpaceX launches supplies to space station (Update)
DoctorBinary
DoctorBinary is offline
#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
hamster143 is offline
#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
DoctorBinary is offline
#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
hamster143 is offline
#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
DoctorBinary is offline
#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
hamster143 is offline
#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
DoctorBinary is offline
#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
DoctorBinary is offline
#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
powers Introductory Physics Homework 7
Powers of Ten General Discussion 3
never done logarithms General Math 5
Powers of Ten Biology 5