In my article “Patterns in the Last Digits of the Positive Powers of Five” I noted that the positive powers of five modulo 10m cycle with period 2m-2, m ≥ 2, starting at 5m. In this article, I’ll present my proof, which has two parts:
- Part 1 shows that the powers of five mod 2m cycle with period 2m-2, m ≥ 2, starting at 50.
- Part 2 shows that the powers of five mod 10m cycle with the same period as the powers of five mod 2m, starting at 5m.
The highlight of my proof is in part 1, where I derive a formula to show that the period, or order, of 5 mod 2m is 2m-2. While it is in general not possible to derive a formula for the order of a number, I’ll show it is possible for the powers of five mod 2m — due to a hidden, binary structure I’ve uncovered.
To understand the proof, you’ll need to know some algebra and the basics of modular arithmetic.
Part 1: Period mod 2m is 2m-2
Part 1 shows that the order of 5 mod 2m is 2m-2. I break it into three steps, showing that
- The order of 5 mod 2m is a power of two. This constrains the values for the order so that only expressions of the form 52n – 1 need be considered.
- 52n – 1 can be factored to isolate its factors of two. This is my key insight, made possible by recursive factoring of differences of squares.
- 52n – 1 is divisible by 2n+2. This shows that the order of 5 mod 2n+2 is 2n, or equivalently, that the order of 5 mod 2m is 2m-2.
In addition, I show that the powers of five mod 2m cycle starting at 50; this is important because it will show that the cycle mod 10m always starts after the cycle mod 2m.
The Order of 5 mod 2m is a Power of Two
The order of a mod b is related to , so let’s start there. is Euler’s phi function, the number of positive integers less than or equal to b that are relatively prime to b (for b a power of two, this is just the count of the odd numbers less than b). We want to compute , which we can do with this simple formula: . For p=2, this gives = 2m-1.
The order of a mod b must divide , so the order of the powers of five mod 2m must divide , or 2m-1. In other words, the order must be a power of two — a power of two less than or equal to 2m-1 to be specific — because the divisors of a positive power of two are all the positive powers of two less than or equal to it.
Let 2e represent any of the candidates for the order of 5 mod 2m: 1, 2, 4, 8, … , 2m-2, 2m-1. By definition, if the order is 2e, , or equivalently, . That is, 52e – 1 is divisible by 2m. Now all we have to do is figure out which e makes this true.
52n – 1 Can Be Factored to Isolate its Factors of Two
You can factor 52n – 1 into (52n/2 + 1)(52n/2 – 1), since it is a difference of two squares. You can factor 52n/2 – 1 similarly, into (52n/4 + 1)(52n/4 – 1). You can do this n times, since log2(2n) = n. Here’s an example:
- 516 – 1 = (58 + 1)(58 – 1)
- 58 – 1 = (54 + 1)(54 – 1)
- 54 – 1 = (52 + 1)(52 – 1)
- 52 – 1 = (51 + 1)(51 – 1)
- 51 – 1 = 4
Combining these recursively you get 516 – 1 = 4(51 + 1)(52 + 1)(54 + 1)(58 + 1).
This generalizes to 52n – 1 = 4(51 + 1)(52 + 1)(54 + 1)···(52n/2 + 1).
There is a factor of two in each 52f + 1, as I’ll show in the next section.
52n – 1 is divisible by 2n+2
The factor of four in the factored expression shows there are at least two factors of two in 52n – 1. There is also exactly one factor of two in each of the factors 52f + 1. I’ll show it in two steps:
- 52f + 1 is divisible by 2.
Every positive power of five ends in 5, so it is odd. This means 52f + 1 is even, meaning it’s divisible by 2.
- 52f + 1 is not divisible by any power of two greater than 2.
To show this, it suffices to show that 52f + 1 is not divisible by 4. If it’s not divisible by 4, it’s not divisible by any higher power of two (because the divisors of a positive power of two are all positive powers of two less than or equal to it). So if 22 is not a factor, 2s, s > 1, is not a factor.
Let’s show 52f + 1 is not divisible by 4 by breaking it in two cases:
- 520 + 1. 51 + 1 = 6, which obviously is not divisible by 4.
- 52f + 1, f ≥ 1. 52f ends in 25, so 52f + 1 ends in 26. An integer is divisible by 4 if and only if its last two digits are divisible by 4. Since 26 is not divisible by 4, neither is 52f + 1.
So the example expression 4(51 + 1)(52 + 1)(54 + 1)(58 + 1) has a factor of 26: 22 times four factors of 2.
This generalizes to show that 52n – 1 is divisible by 2n+2. Recasting this from the perspective of the power of five to the modulus, let’s substitute m-2 for n. This gives the equivalent statement 52m-2 – 1 is divisible by 2m. Just to be explicit, this implies that no 52e, e < 2m-2, is divisible by 2m. So, the candidate power of two we were seeking is 2m-2, the order of 5 mod 2m.
The Powers of Five Mod 2m Cycle Starting at 50
Let the period p = 2m-2. As we proved above, . We also know, trivially, that . The difference between the exponents p and 0 is p, showing a full cycle occurs starting at 50.
Part 2: Period mod 10m is 2m-2
Part 2 shows, using the definition of modular arithmetic, the laws of exponents, and simple algebra, that the powers of five mod 10m have the same period as the powers of five mod 2m. It’s broken into two halves, showing that
- The period mod 2m is a cycle mod 10m.
- The cycle mod 10m is the period mod 2m.
The first half only shows that the period mod 2m 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 2m.
I’ll use the variable p for the period mod 2m, as above, to simplify the notation in the proof that follows.
The period mod 2m is a cycle mod 10m
For i ≥ 0, what we’ve shown is that . That is, powers of five with exponents a period apart are congruent mod 2m.
Congruence mod 2m means that 5i+p – 5i is a multiple of 2m; that is, 5i+p – 5i = n·2m, for some nonnegative integer n.
Factoring out 5i we get 5i(5p – 1) = n·2m. When i≥m, n is a multiple of 5m, so n = n’·5m.
Substituting n’·5m for n we get 5i(5p – 1) = n’·5m2m = n’·10m.
Reversing the process above, we can show congruence mod 10m:
5i(5p – 1) = 5i+p – 5i = n’·10m.
This shows that for i≥m, , so p is a cycle mod 10m.
The cycle mod 10m is the period mod 2m
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:
5i+p – 5i = n·10m = n·5m2m = (n·5m)2m.
This shows that for i≥m, , so p is the period mod 2m and mod 10m.
This section is not part of the proof, but it shows some PARI/GP calculations that support it.
Compute the order of 5 mod 2 through 5 mod 216 (you can see they’re powers of two):
? for(m=1,16,print(znorder(Mod(5,2^m)))) 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384
Show the factors in 516 – 1:
? factor(5^16-1) %1 = [2 6] [3 1] [13 1] [17 1] [313 1] [11489 1] ? factor(4*(5^1+1)*(5^2+1)*(5^4+1)*(5^8+1)) %2 = [2 6] [3 1] [13 1] [17 1] [313 1] [11489 1] ? factor((5^1+1)) %3 = [2 1] [3 1] ? factor((5^2+1)) %4 = [2 1] [13 1] ? factor((5^4+1)) %5 = [2 1] [313 1] ? factor((5^8+1)) %6 = [2 1] [17 1] [11489 1]
Show the factors of two in 5n – 1, n = 1 to 32 (you can see how the nested cycles correspond to the powers of two):
? for(i=1,32,print("5^",i,"-1 has factor 2^",factor(5^i-1)[1,2])) 5^1-1 has factor 2^2 5^2-1 has factor 2^3 5^3-1 has factor 2^2 5^4-1 has factor 2^4 5^5-1 has factor 2^2 5^6-1 has factor 2^3 5^7-1 has factor 2^2 5^8-1 has factor 2^5 5^9-1 has factor 2^2 5^10-1 has factor 2^3 5^11-1 has factor 2^2 5^12-1 has factor 2^4 5^13-1 has factor 2^2 5^14-1 has factor 2^3 5^15-1 has factor 2^2 5^16-1 has factor 2^6 5^17-1 has factor 2^2 5^18-1 has factor 2^3 5^19-1 has factor 2^2 5^20-1 has factor 2^4 5^21-1 has factor 2^2 5^22-1 has factor 2^3 5^23-1 has factor 2^2 5^24-1 has factor 2^5 5^25-1 has factor 2^2 5^26-1 has factor 2^3 5^27-1 has factor 2^2 5^28-1 has factor 2^4 5^29-1 has factor 2^2 5^30-1 has factor 2^3 5^31-1 has factor 2^2 5^32-1 has factor 2^7
(The pattern of the powers of two is reminiscent of the representation of powers of two in a binary counter.)
Part 2 of the proof is identical to part 2 of the proof in my article “Cycle Length of Powers of Two Mod Powers of Ten”, except that 5 and 2 are interchanged. Part 1 is quite different though. I could not use the same approach, since powers of two beyond four don’t have primitive roots.
Coming up with an alternate approach took some time. I had the elements of it early on: knowing that the order must be a power of two, knowing how to factor differences of squares, and knowing that each factor was even. But I was missing the piece that let me show each factor had exactly one factor of two — until I realized I could apply the divisibility by four test.
The binary structure of powers of a number computed mod powers of two make this approach possible (it should work for powers of any odd number, although it may be more difficult to show the factors of two).
To prove the period formula for the positive powers of five mod powers of ten, I first proved it for mod powers of two. I showed that the period must be a power of two, and derived an expression that showed which power of two. I then showed that the period mod powers of two and mod powers of ten must be the same, after a certain starting point.
I’ve previously shown a connection between the positive powers of five and negative powers of two; now I’ve shown a connection between the positive powers of five and the positive powers of two.