Cycle Length of Powers of Two Mod Powers of Ten

http://www.exploringbinary.com/cycle-length-of-powers-of-two-mod-powers-of-ten/


In my article “Patterns in the Last Digits of the Positive Powers of Two” I noted that the positive powers of two modulo 10m cycle with period 4·5m-1, starting at 2m. For example, the powers of two mod 10 cycle with period four: 2, 4, 8, 6, 2, 4, 8, 6, … . In this article, I’ll present my proof, which has two parts:

  • Part 1 shows that the powers of two mod 5m cycle with period 4·5m-1, starting at 20.
  • Part 2 shows that the powers of two mod 10m cycle with the same period as the powers of two mod 5m, starting at 2m.

To understand the proof, you’ll need to know some elementary number theory.

Part 1: Period mod 5m is 4·5m-1

The main goal of part 1 is to show that two is a primitive root mod powers of five, meaning that the order of 2 mod 5m is the value of Euler’s phi function for 5m. I break this into three steps, showing that

  • \mbox{\footnotesize{\displaystyle{\varphi (5^m)}}} = 4·5m-1, where \mbox{\footnotesize{\displaystyle{\varphi (n)}}} is Euler’s phi function (also known as Euler’s totient function).
  • 2 is a primitive root mod 5.
  • 2 is a primitive root mod 5m.

In addition, I show that the powers of two mod 5m cycle starting at 20; this is important because it will show that the cycle mod 10m always starts after the cycle mod 5m.

\mbox{\footnotesize{\displaystyle{\bf{\varphi (5^m)}}}} = 4·5m-1

\mbox{\footnotesize{\displaystyle{\varphi (n)}}} is the number of positive integers less than or equal to n that are relatively prime to n. For a power of a prime number p, we can use this formula to compute it: \mbox{\footnotesize{\displaystyle{\varphi (p^m) = (p \,$-$ 1) \cdot p^{m\,\textnormal{-}1}}}}. For p=5, this gives \mbox{\footnotesize{\displaystyle{\bf{\varphi (5^m)}}}} = 4·5m-1.

2 is a Primitive Root Mod 5

To prove this, we just have to show that the order (also known as multiplicative order) of 2 mod 5 is equal to \mbox{\footnotesize{\displaystyle{\varphi (5)}}}.

\mbox{\footnotesize{\displaystyle{\varphi (5)}}} = 4, by the formula above. The order of 2 mod 5 — the smallest exponent a such that \mbox{\footnotesize{\displaystyle{2^a \equiv 1 \pmod{5}}}} — is four, as shown by the following sequence of four calculations:

  1. \mbox{\footnotesize{\displaystyle{2^1 \equiv 2 \pmod{5}}}}
  2. \mbox{\footnotesize{\displaystyle{2^2 \equiv 4 \pmod{5}}}}
  3. \mbox{\footnotesize{\displaystyle{2^3 \equiv 3 \pmod{5}}}}
  4. \mbox{\footnotesize{\displaystyle{2^4 \equiv \textbf{1} \pmod{5}}}}

Thus, 2 is a primitive root mod 5.

2 is a Primitive Root Mod 5m

To show that 2 is a primitive root mod all positive powers of 5, we can use this result from page 26 of “A Course in Computational Algebraic Number Theory” by Henri Cohen:

“…to find a primitive root modulo pa for p an odd prime and a ≥ 2, proceed as follows: first compute g a primitive root modulo p …, then compute g1 = gp-1 mod p2. If g1 ≠ 1, g is a primitive root modulo pa for every a…” .

In our case g = 2 and p = 5. We’ve already shown 2 to be a primitive root mod 5, so now all we need to show is that \mbox{\footnotesize{\displaystyle{2^{5\,\textnormal{-}1} \not \equiv 1 \pmod{5^2}}}}, which is trivial: \mbox{\footnotesize{\displaystyle{2^4 \equiv 16 \pmod{25}}}}.

So, 2 is a primitive root mod 5m, which means that the order of 2 mod 5m is \mbox{\footnotesize{\displaystyle{\varphi (5^m)}}}. This proves that the powers of two mod 5m cycle with period 4·5m-1.

The Powers of Two Mod 5m Cycle Starting at 20

Let the period p = 4·5m-1. \mbox{\footnotesize{\displaystyle{2^p \equiv 1 \pmod{5^m}}}}, since 2 is a primitive root mod powers of 5 (Euler’s theorem applies). We also know, trivially, that \mbox{\footnotesize{\displaystyle{2^0 \equiv 1 \pmod{5^m}}}}. The difference between the exponents p and 0 is p, showing a full cycle occurs starting at 20.

Part 2: Period mod 10m is 4·5m-1

Part 2 shows, using the definition of modular arithmetic, the laws of exponents, and simple algebra, that the powers of two mod 10m have the same period as the powers of two mod 5m. It’s broken into two halves, showing that

  • The period mod 5m is a cycle mod 10m.
  • The cycle mod 10m is the period mod 5m.

The first half only shows that the period mod 5m is a multiple of the period mod 10m. The second half shows that the period mod 10m is in fact the same as the period mod 5m.

I’ll use the variable p for the period mod 5m, as above, to simplify the notation in the proof that follows.

The period mod 5m is a cycle mod 10m

For i ≥ 0, what we’ve shown is that \mbox{\footnotesize{\displaystyle{2^{i+p} \equiv 2^i \pmod{5^m}}}}. That is, powers of two with exponents a period apart are congruent mod 5m.

Congruence mod 5m means that 2i+p – 2i is a multiple of 5m; that is, 2i+p – 2i = n·5m, for some nonnegative integer n.

Factoring out 2i we get 2i(2p – 1) = n·5m. When i≥m, n is a multiple of 2m, so n = n’·2m.

Substituting n’·2m for n we get 2i(2p – 1) = n’·2m5m = n’·10m.

Reversing the process above, we can show congruence mod 10m:

2i(2p – 1) = 2i+p – 2i = n’·10m.

This shows that for i≥m, \mbox{\footnotesize{\displaystyle{2^{i+p} \equiv 2^i \pmod{10^m}}}}, so p is a cycle mod 10m.

The cycle mod 10m is the period mod 5m

We’ve shown that p is a cycle mod 10m, but not that p is the period mod 10m. In other words, it’s possible the period mod 10m is less than p — we have to show it isn’t.

For i ≥ m, we’ve shown that \mbox{\footnotesize{\displaystyle{2^{i+p} \equiv 2^i \pmod{10^m}}}}. Using the argument above, congruence mod 10m means that:

2i+p – 2i = n·10m = n·2m5m = (n·2m)5m.

This shows that for i≥m, \mbox{\footnotesize{\displaystyle{2^{i+p} \equiv 2^i \pmod{5^m}}}}, so p is the period mod 5m and mod 10m.

Empirical Evidence that 2 is a Primitive Root mod 5m

This section is not part of the proof, but it shows some PARI/GP calculations that support it.

These two commands show indirectly that 2 is a primitive root mod 5 through mod 520, by showing that the order equals Euler’s phi function:

? for(m=1,20,print(eulerphi(5^m)))
4
20
100
500
2500
12500
62500
312500
1562500
7812500
39062500
195312500
976562500
4882812500
24414062500
122070312500
610351562500
3051757812500
15258789062500
76293945312500

? for(m=1,20,print(znorder(Mod(2,5^m))))
4
20
100
500
2500
12500
62500
312500
1562500
7812500
39062500
195312500
976562500
4882812500
24414062500
122070312500
610351562500
3051757812500
15258789062500
76293945312500

This command shows directly that 2 is a primitive root mod powers of 5, using PARI/GP’s znprimroot() function (znprimroot only returns the lowest primitive root, which luckily for us is 2):

? for(m=1,20,print(znprimroot(5^m)))
Mod(2, 5)
Mod(2, 25)
Mod(2, 125)
Mod(2, 625)
Mod(2, 3125)
Mod(2, 15625)
Mod(2, 78125)
Mod(2, 390625)
Mod(2, 1953125)
Mod(2, 9765625)
Mod(2, 48828125)
Mod(2, 244140625)
Mod(2, 1220703125)
Mod(2, 6103515625)
Mod(2, 30517578125)
Mod(2, 152587890625)
Mod(2, 762939453125)
Mod(2, 3814697265625)
Mod(2, 19073486328125)
Mod(2, 95367431640625)

Summary

To prove the period formula for the positive powers of two mod powers of ten, I first proved it for mod powers of five. I showed that two is a primitive root mod powers of five, meaning that the period formula is Euler’s phi function for the powers of five. I then showed that the period mod powers of five and mod powers of ten must be the same, after a certain starting point.

References

These are the main influences behind my proof:

Dingbat

Leave a Comment

(To reduce spam, cookies must be enabled)


css.php