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**cycle with period 2^{m}^{m-2}, m ≥ 2,**starting at 5**.^{0} - Part 2 shows that the powers of five
**mod 10**cycle with the same period as the powers of five mod 2^{m}^{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**. This constrains the values for the order so that only expressions of the form 5^{m}is a power of two^{2n}– 1 need be considered.**5**. This is my key insight, made possible by recursive factoring of differences of squares.^{2n}– 1 can be factored to isolate its factors of two**5**. This shows that the order of 5 mod 2^{2n}– 1 is divisible by 2^{n+2}^{n+2}is 2^{n}, 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^{0}; 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^{2n} – 1 Can Be Factored to Isolate its Factors of Two

You can factor 5^{2n} – 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}(2^{n}) = n. Here’s an example:

- 5
^{16}– 1 = (5^{8}+ 1)(5^{8}– 1) - 5
^{8}– 1 = (5^{4}+ 1)(5^{4}– 1) - 5
^{4}– 1 = (5^{2}+ 1)(5^{2}– 1) - 5
^{2}– 1 = (5^{1}+ 1)(5^{1}– 1) - 5
^{1}– 1 = 4

Combining these recursively you get 5^{16} – 1 = 4(5^{1} + 1)(5^{2} + 1)(5^{4} + 1)(5^{8} + 1).

This generalizes to 5^{2n} – 1 = 4(5^{1} + 1)(5^{2} + 1)(5^{4} + 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^{2n} – 1 is divisible by 2^{n+2}

The factor of four in the factored expression shows there are at least two factors of two in 5^{2n} – 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 2Every 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 2To 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^{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**. 5^{20}+ 1^{1}+ 1 = 6, which obviously is not divisible by 4.**5**. 5^{2f}+ 1, f ≥ 1^{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} + 1)(5^{2} + 1)(5^{4} + 1)(5^{8} + 1) has a factor of 2^{6}: 2^{2} times four factors of 2.

This generalizes to show that 5^{2n} – 1 is divisible by 2^{n+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^{0}

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^{0}.

## 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^{i} is a multiple of 2^{m}; that is, 5^{i+p} – 5^{i} = n·2^{m}, for some nonnegative integer n.

Factoring out 5^{i} we get 5^{i}(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^{i}(5^{p} – 1) = n’·5^{m}2^{m} = n’·10^{m}.

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

5^{i}(5^{p} – 1) = 5^{i+p} – 5^{i} = 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^{i} = n·10^{m} = n·5^{m}2^{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^{16} (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^{16} – 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^{n} – 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^25^2-1 has factor 2^35^3-1 has factor 2^25^4-1 has factor 2^45^5-1 has factor 2^2 5^6-1 has factor 2^3 5^7-1 has factor 2^25^8-1 has factor 2^55^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^25^16-1 has factor 2^65^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^25^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.

Hey, could I use this? — with credit given of course.

I would be using it to prove something about the powers of 5, and this could come in handy.

my work is still in process, but you can check it out on the blog that i gave as website.

I will use you as a source and also print your proof there too, but in my words. unless you tell me otherwise. I will still link this page and also mention your name.

@Mayur,

Yes. Thanks for your interest. I look forward to your blog post.