What does Fermat’s Little Theorem state?

by Theresa Sittel / Friday, 16 May 2025 / Published in Cybersecurity, EITC/IS/CCF Classical Cryptography Fundamentals, Introduction to public-key cryptography, Number theory for PKC – Euclidean Algorithm, Euler’s Phi Function and Euler’s Theorem

Fermat's Little Theorem is a foundational result in number theory and plays a significant role in the theoretical underpinnings of public-key cryptography, particularly in the context of algorithms such as RSA. Let us analyze the theorem, its statement, and its didactic value, specifically within the context of cryptography and number theory.

Correct Statement of Fermat’s Little Theorem (FLT):

Fermat’s Little Theorem states:

If $p$ is a prime number and $a$ is any integer, then

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

or equivalently,

$p \mid (a^p - a)$

This means that $a^p - a$ is divisible by $p$ for any integer $a$ when $p$ is prime.

Clarification

One can ask in particular whether Fermat's Little Theorem states that for any prime $p$ and any integer $a$ , $a^p - a$ is an integer multiple of $p$ . This interpretation is accurate and matches the second expression above: $p \mid (a^p - a)$ .

Explanation and Proof:

The theorem’s assertion is best understood through two principal scenarios:

1. When $p$ does not divide $a$ :
– In this case, $a$ and $p$ are coprime. Fermat’s Little Theorem directly states:

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

Multiplying both sides by $a$ ,

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

indicating $p \mid (a^p - a)$ .

2. When $p$ divides $a$ :
– Let $a = kp$ for some integer $k$ .
– Then $a^p = (kp)^p = k^p p^p$ , which is clearly divisible by $p$ .
– $a^p - a = k^p p^p - kp = kp(p^{p-1} k^{p-1} - 1)$ , which is divisible by $p$ .
– More simply, since both $a^p$ and $a$ are divisible by $p$ , their difference is also divisible by $p$ .

Therefore, in both cases, the theorem holds for any integer $a$ .

Didactic Value and Historical Context:

Fermat's Little Theorem is a key result that demonstrates the unique behavior of primes in modular arithmetic. It is often one of the first theorems demonstrating the interplay between exponentiation and modular congruence. Its application in cryptography, particularly in primality testing and public-key schemes, cannot be overstated.

– Primality Testing: FLT serves as the basis for some probabilistic primality tests. If for some $a$ , $a^p \not\equiv a \pmod{p}$ , then $p$ is definitely composite.
– Public-Key Cryptography: RSA and related algorithms rely on the difficulty of problems in modular exponentiation and the properties of primes as outlined by the theorem.

Examples:

Let us consider some explicit instances to illustrate the theorem:

1. Example 1: $p = 5, a = 2$

$2^5 = 32, \quad 32 - 2 = 30$

$30$ is divisible by $5$ ( $30 / 5 = 6$ ), confirming the theorem.

2. Example 2: $p = 7, a = 3$

$3^7 = 2187, \quad 2187 - 3 = 2184$

$2184$ divided by $7$ yields $312$ , a whole number.

3. Example 3: $p = 11, a = 11$

$11^{11} - 11$

Both $11^{11}$ and $11$ are divisible by $11$ , so their difference is divisible by $11$ .

4. Example 4: $p = 13, a = 26$

$26^{13} - 26$

Since $26$ is divisible by $13$ , both $26^{13}$ and $26$ are, and their difference is as well.

Generalizations and Related Theorems:

– Euler’s Theorem: For any integer $a$ coprime to $n$ , $a^{\varphi(n)} \equiv 1 \pmod{n}$ , where $\varphi(n)$ is Euler’s totient function. FLT is a special case with $n = p$ prime ( $\varphi(p) = p-1$ ).
– Carmichael Function: The smallest exponent $\lambda(n)$ such that $a^{\lambda(n)} \equiv 1 \pmod{n}$ for all $a$ coprime to $n$ . Again, FLT is a particular instantiation for prime $n$ .

Role in Cryptography:

– RSA Algorithm: Although RSA relies more directly on Euler’s theorem, FLT is used for theoretical justifications. RSA’s security assumptions are tied to the difficulty of factoring large composite numbers, but the correctness of the encryption and decryption processes fundamentally depends on properties like those in FLT.
– Diffie-Hellman Key Exchange: Modular exponentiation and prime modulus operations in Diffie-Hellman are consistent with behaviors described by FLT and its generalizations.
– Digital Signatures: Schemes like the ElGamal digital signature also depend on properties of primes and modular exponentiation.

Limitations and Caveats:

– Carmichael Numbers: Composite numbers $n$ for which $a^n \equiv a \pmod{n}$ for all $a$ exist; these are called Carmichael numbers. FLT is not bidirectional: if $a^p \equiv a \pmod{p}$ for all $a$ , this does not guarantee $p$ is prime. This is a subtlety important in primality testing.
– Not an Authentication of Primality: While failure of FLT for some $a$ proves compositeness, its satisfaction for many $a$ does not guarantee primality. This is why primality tests using FLT are probabilistic and not deterministic.

Didactic Importance:

– The theorem is often one of the first exposures students have to properties of primes beyond divisibility, highlighting primes’ unique role in modular arithmetics.
– It provides the mathematical foundation for the design and analysis of cryptographic algorithms, particularly those relying on modular exponentiation.
– It is a stepping stone to deeper topics such as group theory, rings, fields, and their applications in cryptography.

Further Illustration:

Let us explicitly calculate a few more instances for greater clarity:

– For $p = 17, a = 10$ : $10^{17} - 10$
– $10^{17}$ is a large number, but using modular arithmetic:

$10^{17} \equiv 10 \pmod{17}$

Therefore, $10^{17} - 10$ is divisible by $17$ .

– For $p = 13, a = 14$ :
– $14^{13} - 14$ is divisible by $13$ .

Mathematical Underpinnings:

The essence of the theorem lies in the properties of the field $\mathbb{Z}_p$ (integers modulo $p$ ), which forms a finite field when $p$ is prime. In such a field, all nonzero elements have multiplicative inverses, enabling the proof of FLT via group theory: the nonzero elements under multiplication form a cyclic group of order $p-1$ . Thus, any element $a \neq 0$ satisfies $a^{p-1} = 1$ in $\mathbb{Z}_p$ , leading to $a^p = a$ .

Application in Modular Inverses:

The theorem can be used to find modular inverses efficiently. If $a$ is not divisible by $p$ , then $a^{p-1} \equiv 1 \pmod{p}$ , so $a^{p-2}$ is the modular inverse of $a$ modulo $p$ . This is used in cryptographic algorithms such as RSA for decryption exponent calculation.

Significance in Algorithm Design:

Algorithms for modular exponentiation and modular inverse calculation routinely leverage FLT. For instance, the so-called “fast exponentiation” exploits the properties described by FLT to compute large powers modulo a prime efficiently, which is integral in cryptographic key generation and operations.

Broader Implications for Cryptography:

The reliability of encryption, digital signature, and key exchange protocols often rests on mathematical properties like those described by FLT. Understanding FLT is thus indispensable for anyone seeking to comprehend the security and soundness of public-key cryptographic systems.

Fermat's Little Theorem can be accurately described by the following statement: for any prime $p$ and any integer $a$ , $a^p - a$ is divisible by $p$ . Its mathematical and cryptographic significance cannot be overstated, serving as a cornerstone for both theoretical and practical developments in the field of number theory and cryptography.

EITCA Academy

What does Fermat’s Little Theorem state?

Other recent questions and answers regarding EITC/IS/CCF Classical Cryptography Fundamentals:

More questions and answers:

EITCA Academy is a part of the European IT Certification framework

Eligibility for EITCA Academy 80% EITCI DSJC Subsidy support

EITCA Academy

LOG IN TO YOUR ACCOUNT

FORGOT YOUR PASSWORD?

CREATE AN ACCOUNT

What does Fermat’s Little Theorem state?

Other recent questions and answers regarding EITC/IS/CCF Classical Cryptography Fundamentals:

More questions and answers:

Eligibility for EITCA Academy 80% EITCI DSJC Subsidy support