Euler's Theorem

Euler's Theorem states that:

If $a$ and $n$ are coprime (i.e., $\gcd(a, n) = 1$), then:

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

Where:

• $\phi(n)$ is Euler's totient function, which counts the number of positive integers less than $n$ that are coprime with $n$.
• $\gcd(a, n) = 1$ means that $a$ and $n$ share no common prime factors.

Proof of Euler's Theorem

Step 1: Understanding Euler's Totient Function

Euler's totient function $\phi(n)$ is defined as the number of integers $k$ in the set $\{ 1, 2, 3, \ldots, n-1 \}$ such that $\gcd(k, n) = 1$.

Step 2: Grouping Elements of the Set

Consider the set $S = \{ a, 2a, 3a, \ldots, \phi(n) \cdot a \} \mod n$. Since $a$ and $n$ are coprime, multiplying each number in the set $\{1, 2, \ldots, \phi(n)\}$ by $a$ results in a permutation of the set $\{ 1, 2, \ldots, \phi(n) \}$ modulo $n$.

In other words, for each $k \in \{ 1, 2, \ldots, \phi(n) \}$, the number $a \cdot k \mod n$ is a unique number in $\{ 1, 2, \ldots, \phi(n) \}$.

Step 3: Product of Elements

Now, consider the product of all elements in the set $\{ 1, 2, 3, \ldots, \phi(n) \}$. This product can be written as:

$P = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot \phi(n) \pmod{n}$

Since multiplying by $a$ results in a permutation of the elements in $\{ 1, 2, 3, \ldots, \phi(n) \}$, the product of elements $a \cdot 1, a \cdot 2, \ldots, a \cdot \phi(n) \mod n$ is congruent to $P$, i.e.,

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

Step 4: Cancelling the Product

Since $\gcd(a, n) = 1$, $a$ has an inverse modulo $n$, which means we can cancel the product $P$ from both sides. This gives us:

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

Thus, we have proved that if $a$ and $n$ are coprime, then $a^{\phi(n)} \equiv 1 \pmod{n}$.

Key Notes

• Euler's Theorem is a generalization of Fermat's Little Theorem, which holds when $n$ is a prime number.
• This theorem is a powerful result in number theory, often used in cryptography, particularly in RSA encryption.

Would you like a more detailed explanation or examples of Euler's Theorem in action? Here's some further exploration:

1. How does Euler's theorem relate to Fermat's Little Theorem?
2. Can Euler's Theorem be applied to composite numbers?
3. How can Euler's theorem be used in RSA cryptography?
4. What is the formula for Euler’s totient function $\phi(n)$?
5. Can Euler’s theorem be extended to other mathematical fields beyond number theory?

Tip: Euler's theorem is a fundamental tool in modular arithmetic and is especially useful in computing large powers modulo $n$ efficiently.