What is Fermat's theorem?

Fermat's theorem, also called Fermat's little theorem, states that $a^p - a$ is an integer multiple of $p$, if $p$ is a prime number and $a$ is an integer. The mathematical form of the theorem is as follows:

Additionally, an alternate form of the above-mentioned equation exists. The mathematical form of Fermat's alternate form is as follows:

It is valid only if the integer $a$ is not divisible by the prime number $p$. This is unlike the original form, which is valid even when the integer $a$ is not divisible by the prime number $p$. The alternate form states that $a^{p-1} - 1$ is an integer multiple of $p$.

The validity of Fermat's theorem

We can check the validity of Fermat's theorem's original and alternate forms by applying different combinations of $a$ and $p$ to the equation.

The original form

To validate the original form, we consider two examples:

Example 1

Given $a = 2$ and $p = 3$, we know that $a$ is not divisible by $p$. Next, we plug the values into the original Fermat equation, as follows:

Now, we simplify it by writing the equation in its original form $a^p - a$, and calculating if the result of this is a multiple of the prime number $p$, as follows:

We can verify that $6$ is a multiple of $3$:

This proves that Fermat's original theorem is valid when $a$ is not divisible by $p$.

Example 2

Given $a = 6$ and $p = 3$, we know that $a$ is divisible by $p$. Next, we plug the values into the original Fermat equation, as follows:

Now, we simplify it by writing the equation in its original form $a^p - a$, and calculating if the result of this is a multiple of the prime number $p$.

We can verify that $210$ is a multiple of $3$:

This proves that Fermat's original theorem is valid when $a$ is divisible by $p$.

The alternate form

To validate the alternate form, we consider two examples.

Example 1

Given $a = 2$ and $p = 5$, we know that $a$ is not divisible by $p$. Next, we plug the values into the alternate Fermat equation, as follows:

Now, we simplify it by writing the equation in its original form $a^{p-1} - 1$, and calculating if the result of this is a multiple of the prime number $p$, as follows:

We can verify that $15$ is a multiple of $5$:

This proves that Fermat's alternate form is valid when $a$ is not divisible by $p$.

Example 2

Given $a = 10$ and $p = 5$, we know that $a$ is divisible by $p$. Next, we plug the values into the alternate Fermat equation, as follows:

Now, we simplify it by writing the equation in its original form $a^{p-1} - 1$, and calculating if the result of this is a multiple of the prime number $p$, as follows:

We can verify that $9999$ is not a multiple of $5$, as it leaves a remainder of $4$ when divided by $9999$. This proves that Fermat's alternate form is not valid when $a$ is not divisible by $p$.

Application

Fermat's theorem is used as an underlying base for Euler's theorem. Euler's theorem is a generalization of Fermat's theorem. It extends Fermat's theorem, which allows it to be used as the base for the RSA algorithm. Thus, Fermat's theorem is a core part of modern-era cryptography.