Period Of Power Sequence

Today we will learn about an interesting property of any power sequence:

$a^0,\ a^1,\ a^2,\ a^3...\ a^n$ $(mod\ P)$ where $a,\ n$ and $P$ are positive integers.

We will see how this works.

It is easy to see that $modulo\ P$ can give $P$ possible values $0,\ 1,\ 2...\ (P-1)$

Therefore, $a^n \pmod{P}$ will have to be any one of the values $0\ \to (P-1)$

Even if each of the values $a^0, a^1, a^2....\ a^{P-1}$ maps to a distinct number in the set $\{0,\ 1, 2...\ (P-1)\}$

Obviously the number $a^P$ will map to some number in the set, to which some previous power of $a$ has mapped. From this point on, that pattern will repeat.

We we take a couple of examples to understand this better.

Let us take the power sequence of $8^n$ $(mod\ 10)$.

We have learnt that $a \times b \pmod{P} \texttip{\equiv}{congruent to} (a \pmod{P}) \times (b \pmod{P})$

$8^0 = 1 \texttip{\equiv}{congruent to} 1 \pmod{10}$

$8^1 \texttip{\equiv}{congruent to} 8^0 \times 8 \texttip{\equiv}{congruent to} 8 \pmod{10}$

$8^2 \texttip{\equiv}{congruent to} 8^1 \times 8 \texttip{\equiv}{congruent to} 64 \texttip{\equiv}{congruent to} 4 \pmod{10}$

$8^3 \texttip{\equiv}{congruent to} 8^2 \times 8 \texttip{\equiv}{congruent to} 4 \times 8 \texttip{\equiv}{congruent to} 32 \texttip{\equiv}{congruent to} 2 \pmod{10}$ we know from the previous step the $8^2 \texttip{\equiv}{congruent to} 4 \pmod{10}$

$8^4 \texttip{\equiv}{congruent to} 8^3 \times 8 \texttip{\equiv}{congruent to} 2 \times 8 \texttip{\equiv}{congruent to} 16 \texttip{\equiv}{congruent to} 6 \pmod{10}$ we know from the previous step the $8^3 \texttip{\equiv}{congruent to} 2 \pmod{10}$

$8^5 \texttip{\equiv}{congruent to} 8^4 \times 8 \texttip{\equiv}{congruent to} 6 \times 8 \texttip{\equiv}{congruent to} 48 \texttip{\equiv}{congruent to} 8 \pmod{10}$

$8^6 \texttip{\equiv}{congruent to} 8^5 \times 8 \texttip{\equiv}{congruent to} 8 \times 8 \texttip{\equiv}{congruent to} 64 \texttip{\equiv}{congruent to} 4 \pmod{10}$

-----------book page break-----------

So, our pattern will continue like $1,\ \underbrace{8,\ 4,\ 2,\ 6,}\ \underbrace{8,\ 4,\ 2,\ 6,}\ \underbrace{8,...}$

A very important observation here is that, if $a$ and $P$ are co-primes then the pattern will repeat starting with $1$.

We will see an example of this here.

Let us say $a = 7$ and $P = 15$

$7^0 \texttip{\equiv}{congruent to} 1 \pmod{15}$

$7^1 \texttip{\equiv}{congruent to} 7 \pmod{15}$

$7^2 \texttip{\equiv}{congruent to} 49 \texttip{\equiv}{congruent to} 4 \pmod{15}$

$7^3 \texttip{\equiv}{congruent to} 7^2 \times 7 \texttip{\equiv}{congruent to} 4 \times 7 \texttip{\equiv}{congruent to} 28 \texttip{\equiv}{congruent to} 13 \pmod{15}$

$7^4 \texttip{\equiv}{congruent to} 7^3 \times 7 \texttip{\equiv}{congruent to} 13 \times 7 \texttip{\equiv}{congruent to} 91 \texttip{\equiv}{congruent to} 1 \pmod{15}$

Now, that we have obtained $1$ as a result, the complete pattern will repeat as we increase the value of the exponent of $7$.

So, our pattern will continue like:

$\underbrace{1,\ 7,\ 4,\ 8,}\ \underbrace{1,\ 7,\ 4,\ 8,}\ \underbrace{1,...}$

Let's do a quick recap of what we learnt toady:

- If you take any integer $a$ and compute the power sequence $a^0,\ a^1,\ a^2 ...\ a^n$, and take the remainder of each of these powers after division by a fixed integer $P$, these remainders will follow a pattern.

- If the number $a$ and $P$ are coprime, then the pattern will repeat from $1$, however if they are not coprime, then the pattern will repeat from a number different from $1$.