# 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.

-

## closed as off-topic by Ricardo Andrade, Andrey Rekalo, Olivier Benoist, Stefan Kohl, Willie WongNov 28 '13 at 12:48

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question does not appear to be about research level mathematics within the scope defined in the help center." – Ricardo Andrade, Andrey Rekalo, Olivier Benoist, Stefan Kohl, Willie Wong
If this question can be reworded to fit the rules in the help center, please edit the question.

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.

-
Thanks Qiaochu. (I got another answer at physicsforums.com/showthread.php?p=2400449#post2400449 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 '09 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/

-
Not sure about the etiquette of accepting your "own " answer... –  Yemon Choi Nov 9 '09 at 20:42