-2
$\begingroup$

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.

Improve this question
$\endgroup$
13
  • $\begingroup$ It's exactly the Chinese Remainder Theorem. $\endgroup$ Commented Oct 17, 2009 at 19:19
  • $\begingroup$ Could you elaborate please? $\endgroup$ Commented Oct 17, 2009 at 20:04
  • $\begingroup$ You know that the powers of two have a certain period mod 5^m. What is their period mod 2^m? $\endgroup$ Commented Oct 17, 2009 at 21:26
  • $\begingroup$ Their ''period'' would always be 1 (powers are always 0). $\endgroup$ Commented Oct 17, 2009 at 22:02
  • 1
    $\begingroup$ 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? $\endgroup$ Commented Oct 17, 2009 at 22:59

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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.) $\endgroup$ Commented Oct 28, 2009 at 13:47
-1
$\begingroup$

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/

Improve this answer
$\endgroup$
3
  • $\begingroup$ From the FAQ: "It's also perfectly fine to ask and answer your own question... Also, we recommend not answering your own question immediately since leaving the question "open" encourages other people to respond to it. You might discover that somebody else has an even better answer!" I think waiting 23 days for other answers was sufficient. Also, I cited a source upon which I based my answer, but it was given in piecemeal fashion in a forum thread. I wrote an article to try to present the answer clearly -- and it was long with lots of math notation -- so I cited it here instead of copying it. $\endgroup$ Commented Nov 9, 2009 at 22:29
  • $\begingroup$ This is also from the FAQ: "you don't earn any reputation for accepting your own answer to a question". So in other words, they're implying it's OK to accept your own answer. $\endgroup$ Commented Nov 9, 2009 at 22:32
  • $\begingroup$ Fair enough. Reverting (i.e. +1) $\endgroup$ Commented Nov 10, 2009 at 18:26

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.