## Euler's Theorem

Here $\phi(n)$ is Euler Phi Function. Read more about Phi Function on this post - Euler Totient or Phi Function.Theorem- Euler's Theorem states that, if $a$ and $n$ are coprime, then $a^{\phi(n)} \equiv 1 (\text{mod n})$ - Wikipedia

### 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$.

We can prove the above lemma in three steps.Lemma- Set $A$ and set $B$ contains the same integers.

**$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.

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.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

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

## No comments:

## Post a Comment

Leave comments for Queries, Bugs and Hugs.