Euler's Theorem
If two integers $ a $ and $ n $ are coprime (i.e., gcd(a, n) = 1), then the following congruence holds: \[a^{\varphi(n)} \equiv 1 \mod n\] where φ(n) is the Euler totient function, which counts the number of integers less than $ n $ that are coprime to $ n $.
Euler's theorem generalizes Fermat's little theorem, making it applicable to moduli that are not necessarily prime.
Fermat’s little theorem states that if $ p $ is a prime number and $ a $ is an integer not divisible by $ p $, then:
\[ a^{p-1} \equiv 1 \mod p \]
However, this only holds when $ p $ is prime.
Euler’s theorem extends this result to any positive integer $ n $ by incorporating Euler’s totient function, $ φ(n) $.
\[a^{\varphi(n)} \equiv 1 \mod n\]
Why is this important? Euler’s theorem plays a key role in RSA cryptography, where the totient function is used to determine exponents for encryption and decryption.
A Practical Example
Let's consider $ n = 20 $, which is not a prime number.
We choose $ a = 3 $, which is coprime to 20.
Now, we compute Euler’s totient function, φ(20).
$$ \phi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right) $$
where \(p_1, p_2, \dots, p_k\) are the prime factors of \(n\).
For $ n = 20 $, the prime factorization is $ 20 = 2^2 \cdot 5 $, meaning the prime factors are $ p_1 = 2 $ and $ p_2 = 5 $.
$$ \phi(20) = 20 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{5}\right) $$
$$ \phi(20) = 20 \cdot \frac{2-1}{2} \cdot \frac{5-1}{5} $$
$$ \phi(20) = 20 \cdot \frac{1}{2} \cdot \frac{4}{5} $$
$$ \phi(20) = 20 \cdot \frac{4}{10} $$
$$ \phi(20) = 2 \cdot 4 $$
$$ \phi(20) = 8 $$
So, Euler’s totient function gives $ \phi(20) = 8 $, meaning that there are 8 numbers less than 20 that are coprime to it.
Verification. The divisors of 20 are: 1, 2, 4, 5, 10, and 20. Excluding these, the numbers that are coprime to 20 are: 1, 3, 7, 9, 11, 13, 17, and 19—eight in total. This confirms that Euler’s totient function correctly gives $$ φ(20) = 8 $$.
Now, let’s verify Euler’s theorem.
\[a^{\varphi(n)} \equiv 1 \mod n\]
$$ 3^{\varphi(20)} \equiv 1 \mod 20 $$
$$ 3^8 \equiv 1 \mod 20 $$
Since we know that \( 3^8 = 6561 \), we check:
$$ 6561 \equiv 1 \mod 20 $$
The remainder when dividing \( 6561 \) by 20 is 1, confirming that \( 6561 \equiv 1 \mod 20 \).
$$ 3^{\varphi(20)} \equiv 1 \mod 20 $$
Thus, Euler’s theorem holds.
And so on.
