Fermat’s and Euler’s Theorem

Definition

Fermat’s Little Theorem and Euler’s Totient Theorem are fundamental pillars of elementary number theory. They provide powerful methods for calculating modular exponents (finding the remainder of a number raised to a large power), which serves as the mathematical backbone for modern digital cryptography.

Main Content

1. Fermat’s Little Theorem

• 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 \pmod{p}$.
• This theorem simplifies the process of finding large powers by reducing the exponent using the prime modulus.

2. Euler’s Totient Theorem

• Euler’s Totient Theorem generalizes Fermat's Little Theorem. It 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.
• The totient function $\phi(n)$ counts the number of integers between $1$ and $n$ that are coprime to $n$.

3. Euler’s Totient Function ($\phi(n)$)

• If $n$ is prime, $\phi(n) = n - 1$.
• If $n = p \times q$ (where $p$ and $q$ are distinct primes), then $\phi(n) = (p-1)(q-1)$.

Visualizing Coprimes for n=6:
Numbers: 1, 2, 3, 4, 5, 6
Coprime to 6: 1, 5 (GCD is 1)
Not Coprime: 2, 3, 4, 6
Result: φ(6) = 2

Working / Process

1. Identify the Modulus and the Exponent

• Determine if the modulus $n$ is a prime number or a composite number.
• If $n$ is prime, apply Fermat’s Little Theorem ($a^{n-1} \equiv 1 \pmod{n}$).
• If $n$ is composite, calculate $\phi(n)$ to apply Euler’s Theorem ($a^{\phi(n)} \equiv 1 \pmod{n}$).

2. Simplify the Exponent

• Divide the large exponent by $\phi(n)$ (or $p-1$).
• Let the large exponent be $E$. If $E = q \cdot \phi(n) + r$, then $a^E \equiv a^r \pmod{n}$.
• This reduction makes the exponent small and easy to compute.

3. Compute the Final Remainder

• Perform the modular exponentiation using the simplified exponent $r$.
• Example: To find $3^{13} \pmod{7}$:
  • Here $n=7$ (prime), $p-1 = 6$.
  • $13 = 2 \times 6 + 1$.
  • So, $3^{13} \equiv 3^1 \equiv 3 \pmod{7}$.

Advantages / Applications

• Cryptography: These theorems are essential for the RSA encryption algorithm, which secures internet communications.
• Primality Testing: They help in determining if a number is prime (e.g., Fermat Primality Test).
• Efficient Computation: They allow computers to solve gargantuan power problems in milliseconds by keeping numbers small via modular arithmetic.

Summary

Fermat’s Little Theorem and Euler’s Totient Theorem are mathematical rules that simplify modular exponentiation by reducing large exponents. Fermat’s theorem specifically addresses prime numbers, while Euler’s theorem extends this logic to composite numbers using the totient function.

Important terms to remember: Modular Arithmetic, Prime Number, Coprime, Totient Function, and RSA Encryption.