Fermat's Little Theorem

Introduction

Fermat's Little Theorem is a fundamental concept in number theory, named after the French mathematician Pierre de Fermat who first stated it in 1640. Despite its "little" name, this theorem has enormous applications in computer science, particularly in cryptography, primality testing, and modular arithmetic.

The theorem provides a powerful relationship between a prime number and an integer not divisible by that prime, allowing us to perform efficient calculations with large numbers in modular arithmetic. This is especially useful in cryptographic algorithms, where we often need to compute values like $a^b \bmod n$ for very large exponents.

The Theorem Statement

Fermat's Little Theorem can be stated in two equivalent ways:

Statement 1: If $p$ is a prime number and $a$ is an integer not divisible by $p$, then:

$a^{p-1} \equiv 1 \pmod p$

Statement 2: For any integer $a$ and a prime number $p$:

$a^p \equiv a \pmod p$

The second form applies to all integers, whereas the first form requires that $a$ is not divisible by $p$.

Understanding the Theorem

To understand why this theorem works, let's consider a simple example:

Let's take $p = 5$ (a prime number) and $a = 2$.

According to Fermat's Little Theorem: $2^{5-1} \equiv 2^4 \equiv 1 \pmod 5$

Let's verify this:

• $2^4 = 16$
• $16 \div 5 = 3$ with remainder $1$
• So $16 \equiv 1 \pmod 5$

This confirms that $2^4 \equiv 1 \pmod 5$, as predicted by the theorem.

Implementation in Code

Let's implement Fermat's Little Theorem in code to verify it for different values:

javascript

function verifyFermatLittleTheorem(a, p) {
  // Ensure p is a prime number (simple check for demonstration)
  if (!isPrime(p)) {
    return `${p} is not a prime number`;
  }
  
  // Check if a is divisible by p
  if (a % p === 0) {
    // For case a divisible by p, verify a^p ≡ a (mod p)
    const leftSide = powerMod(a, p, p);
    return {
      statement: `a^p ≡ a (mod p)`,
      values: `${a}^${p} ≡ ${a} (mod ${p})`,
      leftSide: leftSide,
      rightSide: a % p,
      verified: leftSide === (a % p)
    };
  } else {
    // For case a not divisible by p, verify a^(p-1) ≡ 1 (mod p)
    const leftSide = powerMod(a, p - 1, p);
    return {
      statement: `a^(p-1) ≡ 1 (mod p)`,
      values: `${a}^${p-1} ≡ 1 (mod ${p})`,
      leftSide: leftSide,
      rightSide: 1,
      verified: leftSide === 1
    };
  }
}

// Helper function for modular exponentiation
function powerMod(base, exponent, modulus) {
  if (modulus === 1) return 0;
  
  let result = 1;
  base = base % modulus;
  
  while (exponent > 0) {
    // If exponent is odd, multiply result with base
    if (exponent % 2 === 1) {
      result = (result * base) % modulus;
    }
    
    // Exponent must be even now
    exponent = exponent >> 1; // divide by 2
    base = (base * base) % modulus; // square the base
  }
  
  return result;
}

// Simple primality test
function isPrime(n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 === 0 || n % 3 === 0) return false;
  
  for (let i = 5; i * i <= n; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) {
      return false;
    }
  }
  
  return true;
}

Let's see some examples:

javascript

console.log(verifyFermatLittleTheorem(2, 5));
console.log(verifyFermatLittleTheorem(3, 7));
console.log(verifyFermatLittleTheorem(10, 3));

Output:

{
  statement: 'a^(p-1) ≡ 1 (mod p)',
  values: '2^4 ≡ 1 (mod 5)',
  leftSide: 1,
  rightSide: 1,
  verified: true
}
{
  statement: 'a^(p-1) ≡ 1 (mod p)',
  values: '3^6 ≡ 1 (mod 7)',
  leftSide: 1,
  rightSide: 1,
  verified: true
}
{
  statement: 'a^(p-1) ≡ 1 (mod p)',
  values: '10^2 ≡ 1 (mod 3)',
  leftSide: 1,
  rightSide: 1,
  verified: true
}

Efficient Modular Exponentiation

One of the most important applications of Fermat's Little Theorem is in performing efficient modular exponentiation. When working with large numbers, direct computation of $a^b \bmod n$ would lead to extremely large intermediate results. Instead, we can use the fast modular exponentiation algorithm (as implemented in the powerMod function above).

This algorithm allows us to compute $a^b \bmod n$ with a time complexity of $O(\log b)$ instead of $O(b)$.

Applications of Fermat's Little Theorem

1. Primality Testing - Fermat Primality Test

Fermat's Little Theorem can be used to check if a number is prime. If a number $p$ satisfies the equation $a^{p-1} \equiv 1 \pmod p$ for several randomly chosen values of $a$, then $p$ is likely prime.

javascript

function fermatPrimalityTest(p, iterations = 5) {
  if (p <= 1) return false;
  if (p <= 3) return true;
  if (p % 2 === 0) return false;
  
  for (let i = 0; i < iterations; i++) {
    // Choose random a such that 2 <= a <= p-2
    const a = 2 + Math.floor(Math.random() * (p - 3));
    
    // If a^(p-1) is not congruent to 1 mod p, then p is composite
    if (powerMod(a, p - 1, p) !== 1) {
      return false;
    }
  }
  
  // p is probably prime
  return true;
}

Note: The Fermat primality test is probabilistic. If it returns false, the number is definitely composite. If it returns true, the number is probably prime, with the probability of correctness increasing with more iterations.

2. Multiplicative Inverse in Modular Arithmetic

Fermat's Little Theorem provides a way to find the multiplicative inverse of a number in modular arithmetic when the modulus is prime. For a prime $p$ and an integer $a$ not divisible by $p$, the multiplicative inverse of $a$ modulo $p$ is:

$a^{-1} \equiv a^{p-2} \pmod p$

javascript

function modInverse(a, p) {
  if (!isPrime(p)) {
    throw new Error("Modulus must be prime for this method");
  }
  if (a % p === 0) {
    throw new Error("a must not be divisible by p");
  }
  
  return powerMod(a, p - 2, p);
}

// Example
console.log(modInverse(3, 11)); // Output: 4 (because 3 * 4 = 12 ≡ 1 (mod 11))

3. RSA Cryptography

Fermat's Little Theorem plays a crucial role in the RSA cryptography algorithm, particularly in key generation and in proving its correctness. RSA relies on modular exponentiation for both encryption and decryption operations.

Limitations and Carmichael Numbers

While Fermat's Little Theorem provides a necessary condition for primality, it's not sufficient. There exist composite numbers, called Carmichael numbers (like 561), which satisfy the condition of Fermat's Little Theorem for all values of $a$ that are coprime with the number. These numbers can fool the basic Fermat primality test.

javascript

console.log(powerMod(2, 560, 561)); // Output: 1, even though 561 is composite

This is why more sophisticated primality tests like the Miller-Rabin test are preferred for cryptographic applications.

Proof of Fermat's Little Theorem

There are several ways to prove Fermat's Little Theorem. One elegant approach uses the concept of modular arithmetic and group theory.

Consider the set of integers $S = \{1, 2, ..., p-1\}$.

When we multiply each element of $S$ by $a$ and take the result modulo $p$, we get a new set $S' = \{a \cdot 1 \bmod p, a \cdot 2 \bmod p, ..., a \cdot (p-1) \bmod p\}$.

Since $p$ is prime and $a$ is not divisible by $p$, all elements in $S'$ are distinct and none are congruent to 0 modulo $p$. Therefore, $S'$ is just a permutation of $S$.

Multiplying all elements of $S$ gives $(p-1)!$ and multiplying all elements of $S'$ gives $a^{p-1} \cdot (p-1)!$.

Since $S$ and $S'$ contain the same elements (perhaps in different order), their products are the same modulo $p$:

$(p-1)! \equiv a^{p-1} \cdot (p-1)! \pmod p$

Since $p$ is prime, $(p-1)!$ is not divisible by $p$ (by Wilson's theorem), so we can cancel it from both sides:

$a^{p-1} \equiv 1 \pmod p$

And that's Fermat's Little Theorem.

Summary

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 powerful theorem enables:

1. Efficient modular exponentiation
2. Primality testing
3. Computation of modular multiplicative inverses
4. Validation of cryptographic algorithms like RSA

While the theorem itself is relatively simple, its applications are far-reaching and crucial for modern computer science, particularly in cryptography and number theory algorithms.

Exercise Questions

1. Verify Fermat's Little Theorem for $a = 4$ and $p = 11$ using pen and paper.
2. Implement a function that uses Fermat's Little Theorem to check if a number is probably prime with a specified confidence level.
3. If $p = 17$ and $a = 5$, use Fermat's Little Theorem to find the modular multiplicative inverse of $a$ modulo $p$.
4. What is the remainder when $7^{100}$ is divided by 11? (Hint: Use Fermat's Little Theorem to simplify the calculation)
5. Investigate Carmichael numbers and explain why they can fool the Fermat primality test.

Additional Resources

1. Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein - For a comprehensive understanding of number-theoretic algorithms.
2. A Course in Number Theory and Cryptography by Neal Koblitz - For deeper insight into the applications of Fermat's Little Theorem in cryptography.
3. Concrete Mathematics by Graham, Knuth, and Patashnik - For understanding the mathematical foundations behind number theory algorithms.