Fermat’s Theorem, aka Fermat’s Little Theorem, is a special case of #Euler’s Theorem which states:
$$ a^{p-1} = 1 (\mod p) $$
Where:
- \(p\) is a prime, and
- \(GCD(a, p) = 1\) (Greatest Common Divisor (GCD)#).
It is particularly useful in Asymmetric Cryptography and primality testing (to test whether a number is a prime). However, when used as primality test, it has several exceptions, or called as Fermat liars, such as Fermat pseudoprimes \(a > 1\) and Carmichael numbers \(n\) where \(b^n \equiv b \mod n\). The alternatives for it are Miller-Rabin and Solovay-Strassen.