Fermat's little theorem

For example, if a = 2 and p = 7, then 2⁷ = 128, and 128 − 2 = 126 = 7 × 18 is an integer multiple of 7.


If a is not divisible by p, that is, if a is coprime to p, then Fermat's little theorem is equivalent to the statement that a^{p − 1} − 1 is an integer multiple of p, or in symbols:^[1][2] $${\displaystyle a^{p-1}\equiv 1{\pmod {p}}.}$$


For example, if a = 2 and p = 7, then 2⁶ = 64, and 64 − 1 = 63 = 7 × 9 is a multiple of 7.


Fermat's little theorem is the basis for the Fermat primality test and is one of the fundamental results of elementary number theory. The theorem is named after Pierre de Fermat, who stated it in 1640. It is called the "little theorem" to distinguish it from Fermat's Last Theorem.^[3]

Generalizations[edit]

Euler's theorem is a generalization of Fermat's little theorem: For any modulus n and any integer a coprime to n, one has


$${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}},}$$


where φ(n) denotes Euler's totient function (which counts the integers from 1 to n that are coprime to n). Fermat's little theorem is indeed a special case, because if n is a prime number, then φ(n) = n − 1.


A corollary of Euler's theorem is: For every positive integer n, if the integer a is coprime with n, then $${\displaystyle x\equiv y{\pmod {\varphi (n)}}\quad {\text{implies}}\quad a^{x}\equiv a^{y}{\pmod {n}},}$$ for any integers x and y. This follows from Euler's theorem, since, if ${\displaystyle x\equiv y{\pmod {\varphi (n)}}}$, then x = y + kφ(n) for some integer k, and one has $${\displaystyle a^{x}=a^{y+\varphi (n)k}=a^{y}(a^{\varphi (n)})^{k}\equiv a^{y}1^{k}\equiv a^{y}{\pmod {n}}.}$$


If n is prime, this is also a corollary of Fermat's little theorem. This is widely used in modular arithmetic, because this allows reducing modular exponentiation with large exponents to exponents smaller than n.


Euler's theorem is used with n not prime in public-key cryptography, specifically in the RSA cryptosystem, typically in the following way:^[10] if $${\displaystyle y=x^{e}{\pmod {n}},}$$ retrieving x from the values of y, e and n is easy if one knows φ(n).^[11] In fact, the extended Euclidean algorithm allows computing the modular inverse of e modulo φ(n), that is, the integer f such that $${\displaystyle ef\equiv 1{\pmod {\varphi (n)}}.}$$ It follows that $${\displaystyle x\equiv x^{ef}\equiv (x^{e})^{f}\equiv y^{f}{\pmod {n}}.}$$


On the other hand, if n = pq is the product of two distinct prime numbers, then φ(n) = (p − 1)(q − 1). In this case, finding f from n and e is as difficult as computing φ(n) (this has not been proven, but no algorithm is known for computing f without knowing φ(n)). Knowing only n, the computation of φ(n) has essentially the same difficulty as the factorization of n, since φ(n) = (p − 1)(q − 1), and conversely, the factors p and q are the (integer) solutions of the equation x² – (n − φ(n) + 1) x + n = 0.


The basic idea of RSA cryptosystem is thus: If a message x is encrypted as y = x^e (mod n), using public values of n and e, then, with the current knowledge, it cannot be decrypted without finding the (secret) factors p and q of n.


Fermat's little theorem is also related to the Carmichael function and Carmichael's theorem, as well as to Lagrange's theorem in group theory.