Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Oct 19, 2009 #1
    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?

  2. jcsd
  3. Oct 21, 2009 #2
    That was an example for m=1. I should have said, 1 x 4*5^(m-1).
  4. Oct 22, 2009 #3
    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.
  5. Oct 23, 2009 #4
    Nice approach (I guess in a way it's using the CRT implicitly). Thanks.

    I have two questions though:

    1) Isn't i0 = m?

    I see it in examples, but not algebraically. Could you elaborate?
  6. Oct 23, 2009 #5
    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.
  7. Oct 26, 2009 #6
    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).

    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)?
  8. Oct 26, 2009 #7
    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.
  9. Oct 26, 2009 #8
    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!
  10. Nov 9, 2009 #9
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook