Cycle Length of Powers of Five Mod Powers of Ten

In my article “Patterns in the Last Digits of the Positive Powers of Five” I noted that the positive powers of five modulo 10^m cycle with period 2^m-2, m ≥ 2, starting at 5^m. In this article, I’ll present my proof, which has two parts:

• Part 1 shows that the powers of five mod 2^m cycle with period 2^m-2, m ≥ 2, starting at 5⁰.
• Part 2 shows that the powers of five mod 10^m cycle with the same period as the powers of five mod 2^m, starting at 5^m.

The highlight of my proof is in part 1, where I derive a formula to show that the period, or order, of 5 mod 2^m is 2^m-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 2^m — 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 2^m is 2^m-2

Part 1 shows that the order of 5 mod 2^m is 2^m-2. I break it into three steps, showing that

• The order of 5 mod 2^m is a power of two. This constrains the values for the order so that only expressions of the form 5²ⁿ – 1 need be considered.
• 5²ⁿ – 1 can be factored to isolate its factors of two. This is my key insight, made possible by recursive factoring of differences of squares.
• 5²ⁿ – 1 is divisible by 2ⁿ⁺². This shows that the order of 5 mod 2ⁿ⁺² is 2ⁿ, or equivalently, that the order of 5 mod 2^m is 2^m-2.

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

The Order of 5 mod 2^m 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 = 2^m-1.

The order of a mod b must divide , so the order of the powers of five mod 2^m must divide , or 2^m-1. In other words, the order must be a power of two — a power of two less than or equal to 2^m-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 2^e represent any of the candidates for the order of 5 mod 2^m: 1, 2, 4, 8, … , 2^m-2, 2^m-1. By definition, if the order is 2^e, , or equivalently, . That is, 5^2e – 1 is divisible by 2^m. Now all we have to do is figure out which e makes this true.

5²ⁿ – 1 Can Be Factored to Isolate its Factors of Two

You can factor 5²ⁿ – 1 into (5^2n/2 + 1)(5^2n/2 – 1), since it is a difference of two squares. You can factor 5^2n/2 – 1 similarly, into (5^2n/4 + 1)(5^2n/4 – 1). You can do this n times, since log₂(2ⁿ) = n. Here’s an example:

1. 5¹⁶ – 1 = (5⁸ + 1)(5⁸ – 1)
2. 5⁸ – 1 = (5⁴ + 1)(5⁴ – 1)
3. 5⁴ – 1 = (5² + 1)(5² – 1)
4. 5² – 1 = (5¹ + 1)(5¹ – 1)
5. 5¹ – 1 = 4

Combining these recursively you get 5¹⁶ – 1 = 4(5¹ + 1)(5² + 1)(5⁴ + 1)(5⁸ + 1).

This generalizes to 5²ⁿ – 1 = 4(5¹ + 1)(5² + 1)(5⁴ + 1)···(5^2n/2 + 1).

There is a factor of two in each 5^2f + 1, as I’ll show in the next section.

5²ⁿ – 1 is divisible by 2ⁿ⁺²

The factor of four in the factored expression shows there are at least two factors of two in 5²ⁿ – 1. There is also exactly one factor of two in each of the factors 5^2f + 1. I’ll show it in two steps:

• 5^2f + 1 is divisible by 2.
  Every positive power of five ends in 5, so it is odd. This means 5^2f + 1 is even, meaning it’s divisible by 2.
• 5^2f + 1 is not divisible by any power of two greater than 2.
  To show this, it suffices to show that 5^2f + 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 2² is not a factor, 2^s, s > 1, is not a factor.

  Let’s show 5^2f + 1 is not divisible by 4 by breaking it in two cases:

  • 5²⁰ + 1. 5¹ + 1 = 6, which obviously is not divisible by 4.
  • 5^2f + 1, f ≥ 1. 5^2f ends in 25, so 5^2f + 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 5^2f + 1.

So the example expression 4(5¹ + 1)(5² + 1)(5⁴ + 1)(5⁸ + 1) has a factor of 2⁶: 2² times four factors of 2.

This generalizes to show that 5²ⁿ – 1 is divisible by 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 5^2m-2 – 1 is divisible by 2^m. Just to be explicit, this implies that no 5^2e, e < 2^m-2, is divisible by 2^m. So, the candidate power of two we were seeking is 2^m-2, the order of 5 mod 2^m.

The Powers of Five Mod 2^m Cycle Starting at 5⁰

Let the period p = 2^m-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 5⁰.

Part 2: Period mod 10^m is 2^m-2

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

• The period mod 2^m is a cycle mod 10^m.
• The cycle mod 10^m is the period mod 2^m.

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

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

The period mod 2^m is a cycle mod 10^m

For i ≥ 0, what we’ve shown is that . That is, powers of five with exponents a period apart are congruent mod 2^m.

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

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

Substituting n’·5^m for n we get 5ⁱ(5^p – 1) = n’·5^m2^m = n’·10^m.

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

5ⁱ(5^p – 1) = 5^i+p – 5ⁱ = n’·10^m.

This shows that for i≥m, , so p is a cycle mod 10^m.

The cycle mod 10^m is the period mod 2^m

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

For i ≥ m, we’ve shown that . Using the argument above, congruence mod 10^m means that:

5^i+p – 5ⁱ = n·10^m = n·5^m2^m = (n·5^m)2^m.

This shows that for i≥m, , so p is the period mod 2^m and mod 10^m.

Empirical Evidence

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 2¹⁶ (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 5¹⁶ – 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 5ⁿ – 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.)

Discussion

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

Summary

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.