Fermat's Little Theorem And Carmichael Numbers

We will introduce Fermat's Little Theorem here.

Theorem

For any prime number $p$, $a^p \equiv a\ (mod\ p)$, for all $1 \le a \lt p$

Prerequisites

We need to understand a few concepts before we go ahead with the proof of Fermat's Little Theorem.

We can take any natural number $N$, then denote the set of all natural numbers $a \le N$ as $\mathbb{Z}_N$, then $\mathbb{Z}_N$ contains all natural numbers $\{0,\ 1,\ 2,\ ...,\ (N-1)\}$.

Out of these elements we can select all number that are coprime to $N$ and denote the set of those numbers as $\mathbb{Z}_{N^*}$.

The count of elements in $\mathbb{Z}_{N^*}$ is called the order of $\mathbb{Z}_{N^*}$ and is denoted by $\phi(N)$, and is also known as $Euler\ Phi$ or $Euler\ Totient$

Note that the set $\mathbb{Z}_{N^*}$ will always contain the number $1$, since $1$ is considered as coprime to every other natural number becuase $gcd(1,\ r) = 1$ for any natural number $r$.

For every $a\ \epsilon\ \mathbb{Z}_{N^*}$ there exist natural numbers $\omega$ such that $a^\omega \equiv 1\ (mod\ N)$. The smallest positive value of $\omega$ satisfying this condition is called the order of element $a$ in $\mathbb{Z}_{N^*}$.

It can be proven that for every $a$ in $\mathbb{Z}_{N^*}$, $\omega_a$ divides $\phi$

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

Proof

If we take any prime number $P$, then every natural number less than $P$ is a coprime to $P$.

Therefore,

$\mathbb{Z}_{P^*} = \{1,\ 2,\ ...,\ (P-1)\}$

$\phi(P) = P - 1$

If we take any element $a$ from the set $\mathbb{Z}_{P^*}$, raise it to the power $P$, we can write

$a^{\phi} = a^{n\times \omega_a}$ for some integer $n$, because $\phi(P)$ is divisible by $\omega_a$

Taking modulo $P$ we get:

$a^{n\times \omega_a}\ (mod\ P)$

$= (a^{\omega_a})^n\ (mod\ P)$

Since $\omega_a$ is the order of $a$ in $\mathbb{Z}_{P^*}$,

$a^{\omega_a}\ (mod\ P) = 1$

$\therefore (a^{\omega_a})^n\ (mod\ P)$

$= (1)^n\ (mod\ P)$

$\therefore a^{\phi} \equiv 1\ (mod\ P)$

Multiplying both sides by $a$, we get:

$a^{\phi} \times a \equiv a\ (mod\ P)$

$\Rightarrow a^{\phi + 1} \equiv a\ (mod\ P)$

We also, know the for prime number $P$, $\phi(P) = P-1 \Rightarrow \phi(P) + 1 = P$

Therefore we get:

$\Rightarrow a^{\phi + 1} = a^P \equiv a\ (mod\ P)$

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

Usage

One of the major applications of Fermat's Little Theorem is to check the primality of large integers. For a large integer $N$ it is computationally difficult to check for primality with all prime number less than $\sqrt{N}$.

Therefore, it is tested to check if $a^{N-1} \equiv\ 1\ (mod\ N)$ for many values of $a$, and if it passes all the tests, it can be concluded with that $N$ is prime with a high probability. Whereas if it fails for even one value of $a$, the test can be terminated immediately with the conclusion that $N$ is not a prime.

So far we have proven that if a number $N$ is prime, then the above relation holds. Is the reverse true as well? That if the above relation hold for a natural number $N$, is $N$ a prime. The answer is no. There are numbers which satisfy this condition, but are not primes.

These are called $Carmichael\ Numbers$.

Carmichael Numbers

To be able to understand Carmichael Numbers, we need to understand another property of Euler Phi.

For any two natural numbers $a$ and $b$,

$\phi(a) \times \phi(b) = \phi(ab)$ if and only if $a$ and $b$ are coprimes.

Let us take a composite natural number $N = p_1 \times p_2 \times p_3 \times ... \times p_n$ where each $p_i$ is a prime factor of $N$, such that each prime factor occurs only once. These numbers are also called $squarefree$ numbers because these numbers are not divisible by any perfect square.

For such a composite number $N$, if for each $i$, $p_i - 1$ divides $N - 1$ then this number will be a Carmichael Number, and will pass the Fermat's test without being a prime.

Let us see how.

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

If $a$ is coprime to $N$, then $a$ is coprime to all $p_i$, therefore,

$a^{p_i } \equiv a\ (mod\ p_i)$ for each $p_i$

$\Rightarrow a^{-1}.a^{p_i} \equiv 1\ (mod\ p_i)$

$\Rightarrow a^{p_i - 1} \equiv 1\ (mod\ p_i)$

Since $N - 1$ is a multiple of $(p_i - 1)$

$a^{N-1} \equiv 1\ (mod\ p_i)$ for each $p_i$

This means that $a^{N-1} - 1$ is divisible by $p_i$ for all $i$.

Since, all $p_i$s are prime numbers, the smallest possible value of $a^{N-1} - 1$ is the product of all $p_i$.

Therefore, $a^{N-1} - 1$ is divisible by $p_1 \times p_2 \times ... \times p_n$, which is $N$.

Therefore, $a^{N-1} - 1 \equiv 0\ (mod\ N)$

Therefore $a^{N-1} \equiv 1\ (mod\ N)$

The smallest known Carmichael Number is $561$. We will see how.

$561 = 3 \times 11 \times 17$

$\phi(3) = 3 - 1 = 2$

$\phi(11) = 11 - 1 = 10$

$\phi(17) = 17 - 1 = 16$

$\phi(561) = 2 \times 10 \times 16 = 320$

And $561 - 1 = 560$ is divisible by $2$, $10$, and $16$

There are infinitely many Carmichael numbers.

The first few of the Carmichael numbers in ascending order are:

$561 = 3 \times 11\times 17$

$1105 = 5 \times 13 \times 17$

$1729 = 7 \times 13 \times 19$

$2465 = 5 \times 17 \times 29$

$2821 = 7 \times 13 \times 31$

$6601 = 7 \times 23 \times 41$

$8911 = 7 \times 19 \times 67$