# Cycle Length of the Positive Powers of Two Mod Powers of Ten [closed]

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 '09 at 19:19
• Could you elaborate please? – Rick Regan Oct 17 '09 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 '09 at 21:26
• Their ''period'' would always be 1 (powers are always 0). – Rick Regan Oct 17 '09 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 '09 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.

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/