On the remainder of powers of an integer

There’s a certain rule, which says that, when a number “a” divides different powers of another number N i.e. N¹, N², N³ … the remainders appear in cyclic form i.e. they repeat a fixed pattern.

Eg. 3¹ divided by 5 gives a remainder of 3

3² = 9 divided by 5 gives a remainder of 4

3³ = 27 divided by 5 gives a remainder of 2

3⁴ = 81 divided by 5 gives a remainder of 1

3⁵ = 243 divided by 5 gives a remainder of  3

and that’s when the pattern starts repeating (3, 4, 2, 1, 3, 4, 2, 1, 3, 4, 2, 1…)

The proof of this is what will now follow. Note: I will only work with the domain of positive integers in the whole of this proof. 

Denote the remainder of any number x, divided by the number a, by the function R(x).

Now, first take a number  N, which, when divided by a, gives a remainder of r.

R(N) = r

Then, N = an + r (where n is an integer)

Raise N to the p^th power (p being a positive integer)

N^p = (an + r)^p

= (an)^p + ……… + r^p

(by binomial expansion) ---- (1) 

Here, all the terms before r^p have an “a” in them, and are therefore together a multiple of a.

So, N^p = (multiple of a) + r^p

Therefore, r^p divided by a will give the same remainder as when N^p is divided by a. *

i.e. R(r^p) = R(N^p) ---- (2)

Now let us prove something first:

If R(r^x) = R(r^y)

Then R(r^x+1) = R(r^y+1)

Say R(r^x) = R(r^y) = R' 

r^x = n_xa + R'

r^{x+ 1} = r^x . r 

Thus, r^x+1 = (n_xa + R')r = r n_xa + R'r

Similarly, r^y = n_ya + R'

r^y+1 = r^y . r

r^y+1 = (n_ya + R')r = r n_ya + R'r

Then, both r^x+1 and r^y+1 are in the form (multiple of a) + R'r

So R'r divided by a gives the same remainder as r^x+1 divided by a

R'r divided by a also gives the same remainder as r^y+1  divided by a

=> r^x+1 divided by a gives the same remainder as r^y+1 divided by a

R(r^x+1) = R(r^y+1) Proved.

From (2),

If R(N^x) = R(N^y)

Then R(N^x+1) = R(N^y+1) ---- (3)

Take R(N^p) as R. If R is not equal to 0, then R can go from 1, 2, 3, 4, … upto a-1. That is a maximum of a-1 possibilities for the value of R. If every next R is different, then we can have at most (a-1) different R’s, after which, R will repeat a value already obtained before, and the rule stated in (3) will cause R to cycle among its fixed values.

Therefore, in the series R(N), R(N²), R(N³), R(N⁴) etc., we need only find a single repetition in the value of R to ensure that R will repeat in the same fashion ad infinitum.

* Addendum: We can use the rule stated in (2) to simplify finding the remainder of powers of large numbers, for example: 87²⁵ divided by 7.

We note that 87 = 12*7 + 3

Thus, the remainder gotten when 87²⁵ is divided by 7 is the same as the remainder when 3²⁵ is divided by 7. Then,

1. 3 / 7 -> 3 ---(1)

2. 9 / 7 -> 2 ---(2)

3. 27 / 7 -> 6 ---(3)

4. 81 / 7 -> 4 ---(4)

5. 243 / 7 -> 5 ---(5)

6. 729 / 7 -> 1 ---(6)

7. 2187 / 7 -> 3 ---(1)

That’s where the repetition starts. So it starts at 3 and cycles every 6 powers. 25 = 6*4 + 1. Thus, the remainder when 3²⁵ is divided by 7 is 3, and consequently, the remainder when 87²⁵ is divided by 7 is also 3.