Fermat’s Little Theorem ¶
If \(p\) is a prime number, then for any integer \(a\):
\(a^{p} \equiv a \pmod {p}\)
For instance, taking \(a = 2\) and \(p = 7\), we get \(2^7 = 128\), and \(128 − 2 = 126 = 7 × 18\) is an integer multiple of 7.
If \(a\) is not divisible by \(p\) (i.e., if \(a\) is coprime to \(p\)), then:
\(a^{p-1} \equiv 1 \pmod {p}\)
As an example, when \(a = 2\) and \(p = 7\), we have \(2^6 = 64\), and \(64 − 1 = 63 = 7 × 9\), which is a multiple of 7.