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

In summary, the positive powers of 2 mod 5^m cycle with period 4*5^(m-1) and this can be proved by showing that 2 is a primitive root mod powers of 5. To prove the same for powers of 10^m, the Chinese Remainder Theorem (CRT) can be used by considering the powers of 2 mod 2^m, which cycle with period 1. Multiplying the two periods, 1 and 4*5^(m-1), gives a period of 4*5^(m-1) for powers of 10^m. It can also be shown that any period mod 10^m must be a period mod 5
  • #1
DoctorBinary
43
0
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 let's 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?

Thanks.
 
Physics news on Phys.org
  • #2
DoctorBinary said:
... is to multiply the two periods: 1 x 4 = 4.

That was an example for m=1. I should have said, 1 x 4*5^(m-1).
 
  • #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^iWhich proves that two periods are equal.
 
  • #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?


2)
hamster143 said:
It's easy to see that n = n' * 2^i0

I see it in examples, but not algebraically. Could you elaborate?
 
  • #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.
 
  • #6
hamster143 said:
1) Maybe, I wasn't trying to prove that.

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

hamster143 said:
On the other hand, any period mod 10^m must be a period mod 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)?
 
  • #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.
 
  • #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!
 

1. What is the cycle length of the positive powers of two mod powers of ten?

The cycle length of the positive powers of two mod powers of ten is 4.

2. How is the cycle length calculated?

The cycle length is calculated by finding the remainder when positive powers of two are divided by powers of ten. The cycle length will always be the same for any given power of ten, as long as the divisor (power of ten) is greater than the dividend (power of two).

3. Does the cycle length change for different powers of ten?

Yes, the cycle length will change for different powers of ten. As the power of ten increases, the cycle length will also increase.

4. What is the pattern of the cycle length for positive powers of two mod powers of ten?

The pattern for the cycle length is that it will always be a repeating pattern of 4, 4, 4, and so on. This means that the cycle length will always be the same for every 4 powers of ten.

5. Why is the cycle length important to know?

The cycle length is important to know because it helps us understand the relationship between powers of two and powers of ten. It also allows us to predict the remainder when dividing positive powers of two by powers of ten, which can be useful in various mathematical calculations.

Similar threads

Replies
11
Views
366
  • Linear and Abstract Algebra
Replies
1
Views
862
  • Linear and Abstract Algebra
Replies
2
Views
1K
Replies
18
Views
3K
  • Quantum Physics
Replies
3
Views
906
  • Special and General Relativity
Replies
7
Views
340
  • General Math
Replies
7
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
4K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
Replies
5
Views
2K
Back
Top