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

I want to prove that the positive powers of two, mod 10m, cycle with period 4*5m-1. It's simple to prove that the powers of FIVE cycle with this period (2 is a primitive root mod powers of five), but how do you make the leap to powers of TEN?

I'm sure it's something simple -- perhaps related to the Chinese Remainder Theorem -- but I don't see the connection yet.

Thanks for the help.

-
It's exactly the Chinese Remainder Theorem. – Qiaochu Yuan Oct 17 2009 at 19:19
Could you elaborate please? – Rick Regan Oct 17 2009 at 20:04
You know that the powers of two have a certain period mod 5^m. What is their period mod 2^m? – Qiaochu Yuan Oct 17 2009 at 21:26
Their ''period'' would always be 1 (powers are always 0). – Rick Regan Oct 17 2009 at 22:02
So if M is a number which leaves a residue of 1 mod 5^k, and a residue of 0 mod 2^k, what residue does it leave mod 10^k? – Alon Amit Oct 17 2009 at 22:59

And if you insist, let me write this out in detail. All you need is the following lemma.

Lemma: Let f(n) be periodic with period p and let g be injective. Then g(f(n)) is periodic with period p.

Proof. Clearly g(f(n+p)) = g(f(n), so g(f(n)) has some period q dividing p. On the other hand, g(f(n+q)) = g(f(n)) for all n if and only if f(n+q) = f(n) for all n by injectivity, so q = p.

As I remarked above we have bn = b for all but finitely many n and x -> CRT(x, b) is an injection. The result follows.

-
 Thanks Qiaochu. (I got another answer at physicsforums.com/… which you might want to check out. It appeals to me more because it uses algebra and exponent arithmetic and does not use the CRT explicitly.) – Rick Regan Oct 28 2009 at 13:47

The answer I like best is based on the proof in the "physics forums" thread linked to in the comments above. I wrote about it in detail here: http://www.exploringbinary.com/cycle-length-of-powers-of-two-mod-powers-of-ten/

-