Fermat's and Euler's Theorem

Two theorems that play important roles in public-key cryptography are Fermat’s theorem and Euler’s theorem.

Fermat’s Theorem ( Fermat's Little Theorem)

Fermat’s theorem states the following: If $p$ is prime and $a$ is a positive integer not divisible by $p$, then 

$$a^{p-1} \equiv 1 \pmod{p}$$

Proof: Consider the set of positive integers less than $p:\{1,2,\ldots,p-1\}$ and multiply each element by $a$, modulo $p$, to get the set $X=\{a \pmod{p},2a \pmod{p},\ldots,(p-1)a \pmod{p}\}$

None of the elements of $X$ is equal to zero because $p$ does not divide $a$. Furthermore, no two of the integers in $X$ are equal.To see this,assume that $ja \equiv ka \pmod{p}$, where $i \le j \lt k \le (p-1)$. Because $a$ is relatively prime to $p$ , we can eliminate $a$ from both sides of the equation resulting in $j \equiv k \pmod{p}$ .This last equality is impossible, because $j$ and $k$ are both positive integers less than $p$.Therefore, we know that the $(p-1)$ elements of  $X$ are all positive integers with no two elements equal.

So We can conclude the set $X$ consists of the set of integers $[1,2,\dots,p-1]$ in some order. Multiplying the numbers in both sets ( $p$ and  $X$ ) and taking the result mod yields

$$a \times 2a \ldots \times (p-1)a \equiv 1 \times 2 \times \ldots \times p-1 \pmod{p}$$

$$a^{p-1}(p-1)! \equiv (p-1)! \pmod{p}$$

We can cancel the $(p-1)!$ term because it is relatively prime to $p$.This yields Equation $a^{p-1} \equiv 1 \pmod{p}$ which completes the proof.

Example:

An alternative form of Fermat’s theorem is also useful: If  $p$ is prime and $a$ is a positive integer, then

$$a^p \equiv  a \pmod p$$

Example:

Application: This helps in solving large congruence modulo $p$

lets find $2^{68} \pmod{19}$

using Fermat's Theorem $2^{18} \equiv 1 \pmod{19}$

Now $68=18 \times 3 + 14 $

So

$2^{68} \equiv (2^{18})^3 + 2^{14} \pmod{19} \equiv 2^{14} \pmod{19}$

$2^4 \equiv 16 \equiv -3 \pmod{19}$
$2^{14} \equiv 2^4.2^4.2^4.2^2 \equiv -27.4 \equiv -8.4 \equiv =-13 \equiv 6 \pmod{19}$

Therefore

$ 2^{68} \pmod{19} \equiv 6 \pmod{19}$

 

Euler’s Totient Function

Before presenting Euler’s theorem, we need to introduce an important quantity in number theory, referred to as Euler’s totient function, written $\phi(n)$ , and defined as the number of positive integers less than and relatively prime to $n$. By convention,

$$\phi(1) = 1$$

It should be clear that, for a prime number $p$, 

$$\phi(p) = p-1 $$

Now suppose that we have two prime numbers $p$ and $q$ with $p \ne q$. Then we can show that, for $n=pq$

$$\phi(n)=\phi(pq)=\phi(p) \times \phi(q)=(p-1) \times (q-1)$$

To see that $\phi(n)=\phi(p) \times \phi(q)$, consider that the set of positive integers less than $n$ is the set $[1,2,\ldots,(pq-1)]$. The integers in this set that are not relatively prime to $n$ are the set $\{p,2p,\ldots,(q-1)p\}$ and the set $\{q,2q,\ldots,(p-1)q\}$. Accordingly

$$\phi(n)=(pq-1)-[(q-1)+(p-1)]$$

$$\phi(n)=pq-p-q+1$$

$$\phi(n)=(p-1) \times (q-1)$$

$$\phi(n)=\phi(p) \times \phi(q)$$

Example:

Euler's Theorem

Euler’s theorem states that for every $a$ and $n$ that are relatively prime:

$$a^{\phi(n)} \equiv 1 \pmod{n}$$

Proof: The above Equation  is true if $n$ is prime, because in that case,$\phi(n)=n-1$ and Fermat’s theorem holds. However, it also holds for any integer $n$. Recall that $\phi(n)$ is the number of positive integers less than $n$ that are relatively prime to $n$ .Consider the set of such integers, labeled as

$$R=\{x_1,x_2,\ldots,x_{\phi(n)}\}$$

That is, each element  $x_i$ of $R$ is a unique positive integer less than $n$ with $gcd(x_i,n)=1$.Now multiply each element by $a$, modulo $n$:

$$S=\{ax_1 \pmod{n},ax_2 \pmod{n},\ldots,ax_{\phi(n)} \pmod{n}\}$$

The set $S$ is a permutation of  $R$, by the following line of reasoning:

1. Because $a$ is relatively prime to $n$ and $x_i$ is relatively prime to $n$ , $ax_i$ must also be relatively prime to $n$. Thus, all the members of $S$ are integers that are less than $n$ and that are relatively prime to $n$.

2.There are no duplicates in $S$.If $ax_i \pmod{n} = ax_j \pmod{n}$, then $x_i = x_j$

Fermat's little theorem and Euler's theorem can be used for Primality testing.

Fermat's Little Theorem is a fundamental theorem in number theory that states that if $p$ is a prime number and $a$ is an integer not divisible by $p$, then $a^{p-1} \equiv \pmod{1}$. This theorem provides a useful tool in primality testing through what's known as the Fermat primality test.

The Fermat primality test is a probabilistic algorithm used to determine whether a given number is likely prime or composite. It works based on Fermat's Little Theorem as follows:

1.Select a random integer $a$: 
Choose a random integer $a$ such that $1<a<n$, where $n$ is the number being tested for primality.

2.Check if $a^{n−1}≡1\pmod{n}$:
Compute $a^{n−1}\pmod{n}$. If the result is not congruent to 1, then $n$ is definitely composite.

3.Repeat the test with different $a$: 

Repeat steps 1 and 2 with different random values of $a$. If $n$ passes the test for a certain number of randomly chosen $a$ values, it is considered likely prime.

The Fermat primality test is fast and easy to implement. However, it is important to note that it is probabilistic, meaning there's a chance it might incorrectly identify composite numbers as prime (known as a false positive). This occurs when $n$ is a composite number that satisfies $a^{n−1}≡1\pmod {n}$ for all chosen $a$ values. Such composite numbers are called Carmichael numbers.

Despite its probabilistic nature and the existence of Carmichael numbers, the Fermat primality test is still valuable, particularly for large numbers, as it provides a quick way to filter out many composites efficiently. It is often used as a preliminary test before applying more rigorous primality tests, such as the Miller-Rabin primality test or the AKS primality test.

Example:

Check whether the number 9 is prime or not.

choose a number relatively prime to 9 say 2

No as per theorem if $p$ is prime then $a^{p-1} \equiv 1 \pmod{p}$

ie; $2^{8} \equiv 1 \pmod{9}$

$2^8 \pmod{9}=4$

So the number 9 is composite

Check whether the number 7 is prime or not.

choose a number relatively prime to 7 say 2

No as per theorem if $p$ is prime then $a^{p-1} \equiv 1 \pmod{p}$

ie; $2^{6} \equiv 1 \pmod{7}$

$2^6 \pmod{7}=1$

choose another $a =3$

$3^6 \pmod{7}=1$

choose another $a =5$

$5^6 \pmod{7}=1$

We can conclude that 7 is a prime

Note:

561: This is the smallest Carmichael number. It is composite and can be factored as $3×11×17$ It satisfies $a^{560}≡1\pmod{561}$ for all $a$ that are coprime to 561.

Carmichael numbers are relatively rare compared to composite numbers in general, but they are important to consider when designing primality testing algorithms because they can lead to false positives if only relying on Fermat's Little Theorem for primality testing.