We will be looking into two theorems at the same time today, Fermat's Little Theorem and Euler's Theorem. Euler's Theorem is just a generalized version of Fermat's Little Theorem, so they are quite similar to each other. We will focus on Euler's Theorem and its proof. Later we will use Euler's Theorem to prove Fermat's Little Theorem.
Euler's Theorem
Theorem - Euler's Theorem states that, if $a$ and $n$ are coprime, then $a^{\phi(n)} \equiv 1 (\text{mod n})$ - Wikipedia
Here $\phi(n)$ is Euler Phi Function. Read more about Phi Function on this post - Euler Totient or Phi Function.
Proof
Let us consider a set $A = \{b_1, b_2, b_3...,b_{\phi(n)} \}\:(\text{mod n})$, where $b_i$ is coprime to $n$ and distinct. Since there are $\phi(n)$ elements which are coprime to $n$, $A$ contains $\phi(n)$ integers.
Now, consider the set $B = \{ ab_1, ab_2, ab_3....ab_{\phi(n)} \} \:(\text{mod n})$. That is, $B$ is simply set $A$ where we multiplied $a$ with each element. Let $a$ be coprime to $n$.
Lemma - Set $A$ and set $B$ contains the same integers.
We can prove the above lemma in three steps.
- $A$ and $B$ has the same number of elements
Since $B$ is simply every element of $A$ multiplied with $a$, it contains the same number of elements as $A$. This is obvious.
- Every integer in $B$ is coprime to $n$
An integer in $B$ is of form $a \times b_i$. We know that both $b_i$ and $a$ are coprime to $n$, so $ab_i$ is also coprime to $n$.
- $B$ contains distinct integers only
Suppose $B$ does not contain distinct integers, then it would mean that there is such a $b_i$ and $b_j$ such that:
$ab_i \equiv ab_j\:(\text{mod n})$
$b_i \equiv b_j\:(\text{mod n})$
But this is not possible since all elements of $A$ are distinct, that is, $b_i$ is never equal to $b_j$. Hence, $B$ contains distinct elements.
With these three steps, we claim that, since $B$ has the same number of elements as $A$ which are distinct and coprime to $n$, it has same elements as $A$.
Now, we can easily prove Euler's Theorem.
$ab_1 \times ab_2 \times ab_3...\times ab_{\phi(n)} \equiv b_1 \times b_2 \times b_3...\times b_{\phi(n)} \:(\text{mod n})$
$a^{\phi(n)} \times b_1 \times b_2 \times b_3...\times b_{\phi(n)} \equiv b_1 \times b_2 \times b_3...\times b_{\phi(n)} \:(\text{mod n}) $
$$\therefore a^{\phi(n)} \equiv 1 \:(\text{mod n})$$
Fermat's Little Theorem
Fermat's Little Theorem is just a special case of Euler's Theorem.
Theorem - Fermat's Little Theorem states that, if $a$ and $p$ are coprime and $p$ is a prime, then $a^{p-1} \equiv 1 \:(\text{mod p})$ - Wikipedia
As you can see, Fermat's Little Theorem is just a special case of Euler's Theorem. In Euler's Theorem, we worked with any pair of value for $a$ and $n$ where they are coprime, here $n$ just needs to be prime.
We can use Euler's Theorem to prove Fermat's Little Theorem.
Let $a$ and $p$ be coprime and $p$ be prime, then using Euler's Theorem we can say that:
$a^{\phi(p)} \equiv 1\:(\text{mod p})$ (But we know that for any prime $p$, $\phi(p) = p-1$)
$a^{p-1} \equiv 1\:(\text{mod p})$
Conclusion
Both theorems have various applications. Finding Modular Inverse is a popular application of Euler's Theorem. It can also be used to reduce the cost of modular exponentiation. Fermat's Little Theorem is used in Fermat's Primality Test.
There are more applications but I think it's better to learn them as we go. Hopefully, I will be able to cover separate posts for each of the applications.
Reference
- Wiki - Euler's Theorem
- forthright48 - Euler Totient or Phi Function
- Wiki - Fermat's Little Theorem
Labels: Modular Arithmetic, Number Theory, Proof, Theorem