Cycle Length of Powers of Two Mod Powers of Ten
Copyright © 2008-2016 Exploring Binary
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
- = 4·5m-1, where 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.
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: . For p=5, this gives = 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 .
= 4, by the formula above. The order of 2 mod 5 — the smallest exponent a such that — is four, as shown by the following sequence of four calculations:
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 , which is trivial: .
So, 2 is a primitive root mod 5m, which means that the order of 2 mod 5m is . 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. , since 2 is a primitive root mod powers of 5 (Euler’s theorem applies). We also know, trivially, that . 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 . 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, , 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 . 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, , 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)
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.
These are the main influences behind my proof:
- Challenging Mathematical Problems with Elementary Solutions, Volume 1. Page 198: “It can be proved that the last k digits of the number 2n are repeated in groups of 4·5k-1, starting with the number 2k.”
- The USSR Olympiad Problem Book; Selected Problems and Theorems of Elementary Mathematics. Page 57, problem 243, and its answer, on page 354, discuss the case for powers of two mod 1010.
- Question I asked at physicsforums.com. User hamster143‘s proof that the period for powers of five and ten are equal.
- Discussion at physicsforums.com. User shmoe‘s comment: “a power of 2’s congruence class mod 10 is completely determined by its congruence class mod 5”.
- Hakmem Item 57. Two comments by Schroeppel:
- “After the nth, they are all multiples of 2n.”
- “They get into a loop of length 4·5m-1. (Because 2 is a primitive root of powers of 5.)”
- Question I asked at mathoverflow.net.