modulo - Part 5

Today we will learn about Fermat's "little" Theorem. We will see that Fermat's little Theorem is very useful in modulo arithmetic. The theorem asserts that for any prime number $p$ and for any number $a$ not divisible by $p$,
$$a^{p-1} = 1 \pmod{p} .$$



Example:

• with $p=7$ and $a=3$, $$3^6 = 1 \pmod{7}$$
• with $p=13$ and $a=2014$, $$2014^{12} = 1 \pmod{13}$$
• with $p=29$ and $a=15$, $$15^{28} = 1 \pmod{29}$$

Suppose we want to find $3^{n} = ~?~ \pmod{7}$ for a large number $n$. How can we do that?

By Fermat's little Theorem, we know that
$$3^6 = 1 \pmod{7} .$$
To find $3^n \pmod{7}$ for a large number $n$, we take $n$ and divide it by 6. Suppose we have $n = 6k+r$ where $r=0,1,2,3,4,5$, then
$$3^{n} = 3^{6k+r} = (3^6)^k \times 3^r = 1^k \times 3^r = 3^r \pmod{7}$$
So by using Fermat's little Theorem, we have reduced $3^{n}$ to $3^r \pmod{7}$ where $r$ is a small number.

Example: Find $3^{2012}$ modulo $7$. We take $2012$ and divide it by $6$, we have $2012 = 6 \times 335 + 2$, so
$$3^{2012} = 3^{6 \times 335 + 2} = (3^6)^{335} \times 3^2 = 1^{335} \times 3^2 \pmod{7}$$ Therefore, $3^{2012} = 3^2 = 9 = 2 \pmod{7}$.



Let us now prove the Fermat's little Theorem. We first present the proof for a special case that $3^6 = 1 \pmod{7}$ and then prove the general case that $a^{p-1} = 1 \pmod{p}$.

Observe that
$$3 \times 1 = 3 \pmod{7}$$ $$3 \times 2 = 6 \pmod{7}$$ $$3 \times 3 = 2 \pmod{7}$$ $$3 \times 4 = 5 \pmod{7}$$ $$3 \times 5 = 1 \pmod{7}$$ $$3 \times 6 = 4 \pmod{7}$$ So
$$3^6 \times 1 \times 2 \times 3 \times 4 \times 5 \times 6 = 1 \times 2 \times 3 \times 4 \times 5 \times 6 \pmod{7}$$

It implies that
$$(3^6 -1) \times 1 \times 2 \times 3 \times 4 \times 5 \times 6 = 0 \pmod{7}$$

What does this equation mean? It means that $(3^6 -1) \times 1 \times 2 \times 3 \times 4 \times 5 \times 6$ is divisible by 7. Therefore, $3^6 -1$ must also be divisible by 7. In other words, $3^6 = 1 \pmod{7}$. So we have proved the Fermat's little Theorem for the case $p=7$ and $a=3$. Proof for the general case is exactly the same.


Proof of the Fermat's little Theorem. 

Suppose that $p$ is a prime number and $a$ is not divisible by $p$. Consider the numbers: $a$, $2a$, $3a$, $\dots$, $(p-1)a$. We write
$$a = r_1 \pmod{p}$$ $$2a = r_2 \pmod{p}$$ $$3a = r_3 \pmod{p}$$ $$\dots$$ $$(p-1)a = r_{p-1} \pmod{p}$$ where $r_1, r_2, r_3, \dots, r_{p-1}$ are the numbers in the range $[0,p-1]$.

We make two observations.

First of all, $r_i \neq 0$. Why is that? It is because if $r_i=0$ then $ia = r_i = 0 \pmod{p}$. This is impossible because $a$ and $i$ are not divisible by $p$.

The second thing we observe is that the numbers $r_1, r_2, r_3, \dots, r_{p-1}$ must all be different numbers. Why is that? What would happen if $r_i = r_j$? If $r_i = r_j$ then $ia = r_i = r_j = ja \pmod{p}$, so $(i-j)a = 0 \pmod{p}$. This is again impossible because $a$ and $i-j$ are not divisible by $p$.

We have $p-1$ numbers $r_1, r_2, r_3, \dots, r_{p-1}$, they are all different and they are in the range $[1,p-1]$. It follows that these $p-1$ numbers $r_1, r_2, r_3, \dots, r_{p-1}$ must be a permutation of $p-1$ numbers $1,2,3, \dots, p-1$. So $$r_1 \times r_2 \times r_3  \times \dots \times r_{p-1} = 1 \times 2 \times 3 \times \dots \times (p-1) .$$

Multiplying the following equations
$$a = r_1 \pmod{p}$$ $$2a = r_2 \pmod{p}$$ $$3a = r_3 \pmod{p}$$ $$\dots$$ $$(p-1)a = r_{p-1} \pmod{p}$$ we get
$$a^{p-1} \times 1 \times 2 \times \dots \times (p-1) = r_1 \times r_2 \times \dots \times r_{p-1}  = 1 \times 2 \times \dots \times (p-1) \pmod{p}$$

Therefore,
$$(a^{p-1} - 1) \times 1 \times 2 \times \dots \times (p-1) = 0 \pmod{p},$$
and so
$$a^{p-1} - 1 = 0 \pmod{p} .$$
Thus, we have proved the Fermat's little Theorem that $a^{p-1} = 1 \pmod{p}. \blacksquare$




Let us point out a consequence of Fermat's little Theorem. Since $a^{p-1} = 1 \pmod{p}$, if $x$ is the smallest positive number such that $a^x = 1 \pmod{p}$ then $x$ must be a divisor of $p-1$. For example, when $p=7$, by Fermat's little Theorem, we have $$1^6=2^6=3^6=4^6=5^6=6^6 = 1 \pmod{7},$$
the smallest positive number $x$ such that $a^x = 1 \pmod{7}$ for each case is listed below

• $a=1$ then $x=1$  $$1^1 = 1 \pmod{7}$$
• $a=2$ then $x=3$  $$2^1 = 2, ~2^2 = 4, ~2^3 = 8 = 1  \pmod{7}$$
• $a=3$ then $x=6$  $$3^1 = 3, ~3^2 = 9 = 2, ~3^3 = 6, ~3^4 = 18 = 4, ~3^5 = 12 = 5, ~3^6 = 15 = 1  \pmod{7}$$
• $a=4$ then $x=3$  $$4^1 = 4, ~4^2 = 16 = 2, ~4^3 = 8 = 1  \pmod{7}$$
• $a=5$ then $x=6$  $$5^1 = 5, ~5^2 = 25 = 4, ~5^3 = 20 = 6, ~5^4 = 30 = 2, ~5^5 = 10 = 3, ~5^6 = 15 = 1  \pmod{7}$$  
• $a=6$ then $x=2$  $$6^1 = 6, ~6^2 = 36 = 1  \pmod{7}$$

We can see that in each case, $1^1 = 2^3 = 3^6 = 4^3 = 5^6 = 6^2 = 1 \pmod{7}$, the exponent $x = 1, 3, 6, 3, 6, 2$ is a divisor of $p-1=6$. The following figure illustrates the cyclic behavior of $a^n$ modulo 7. 

$a^n$ modulo 7

That's all for now. See you again at "modulo - Part 6".


Homework.

1. Prove that $2011^{2011^{2011}} + 2012^{2012^{2012}} + 2013^{2013^{2013}} + 2014^{2014^{2014}}$ is divisible by 11.

2. Let $p$ be a prime number and $a$ a number not divisible by $p$. Let $x$ be the smallest positive number such that $a^x = 1 \pmod{p}$. Prove that $p-1$ divisible by $x$.

3. Calculate $2^n \pmod{11}$ for each $n=0,1,2,3,\dots$, then state the cyclic behavior of $2^n$ modulo $11$.

Do the same for $3^n$, $4^n, \dots, 10^n$ modulo $11$.