Congruences - Main Theorem

Fermat's Little Theorem and its generalization, Euler's Theorem, are cornerstones of modern number theory and cryptography. These results describe the behavior of powers in modular arithmetic and form the mathematical foundation of the RSA encryption system.

TheoremFermat's Little Theorem

Let $p$ be a prime number, and let $a$ be an integer not divisible by $p$ . Then: $a^{p-1} \equiv 1 \pmod{p}$

Equivalently, for any integer $a$ : $a^p \equiv a \pmod{p}$

Fermat's Little Theorem, first stated by Pierre de Fermat in 1640, provides a simple yet powerful relationship between exponentiation and prime moduli. It has numerous applications, from primality testing to cryptographic protocols.

ExampleFermat's Little Theorem in Action

Let $p = 7$ and $a = 2$ . Then $p - 1 = 6$ , and: $2^6 = 64 = 9 \cdot 7 + 1 \equiv 1 \pmod{7}$

For $a = 3$ : $3^6 = 729 = 104 \cdot 7 + 1 \equiv 1 \pmod{7}$

Using the second form, $2^7 = 128 = 18 \cdot 7 + 2 \equiv 2 \pmod{7}$ .

TheoremEuler's Theorem

Let $n$ be a positive integer, and let $a$ be an integer with $\gcd(a, n) = 1$ . Then: $a^{\phi(n)} \equiv 1 \pmod{n}$ where $\phi(n)$ is Euler's totient function.

Euler's Theorem generalizes Fermat's Little Theorem to arbitrary moduli. When $n = p$ is prime, we have $\phi(p) = p - 1$ , recovering Fermat's result.

ExampleEuler's Theorem

Consider $n = 10$ . We have $\phi(10) = \phi(2 \cdot 5) = \phi(2)\phi(5) = 1 \cdot 4 = 4$ .

For $a = 3$ (with $\gcd(3, 10) = 1$ ): $3^4 = 81 = 8 \cdot 10 + 1 \equiv 1 \pmod{10}$

For $a = 7$ : $7^4 = 2401 = 240 \cdot 10 + 1 \equiv 1 \pmod{10}$

This explains why the last digit of $7^n$ cycles with period $4$ : $7, 9, 3, 1, 7, 9, \ldots$

Remark

Euler's Theorem provides the basis for the RSA cryptosystem. In RSA, we choose distinct primes $p$ and $q$ , set $n = pq$ , and use the fact that: $a^{\phi(n)} \equiv 1 \pmod{n}$ to construct encryption and decryption exponents $e$ and $d$ satisfying $ed \equiv 1 \pmod{\phi(n)}$ . The security relies on the difficulty of factoring $n$ .

TheoremWilson's Theorem

Let $p$ be a prime number. Then: $(p-1)! \equiv -1 \pmod{p}$

Conversely, if $(n-1)! \equiv -1 \pmod{n}$ for some integer $n > 1$ , then $n$ is prime.

Wilson's Theorem provides a characterization of prime numbers, though it is not practical for primality testing due to the computational cost of computing large factorials.

ExampleWilson's Theorem

For $p = 5$ : $4! = 24 = 5 \cdot 5 - 1 \equiv -1 \pmod{5}$

For $p = 7$ : $6! = 720 = 103 \cdot 7 - 1 \equiv -1 \pmod{7}$

For the composite number $n = 6$ : $5! = 120 = 20 \cdot 6 \equiv 0 \not\equiv -1 \pmod{6}$

This confirms that $6$ is not prime.

These classical theorems illuminate the deep arithmetic structure underlying modular exponentiation and continue to find new applications in modern mathematics and computer science.