# Fermat’s Little Theorem Co-prime Condition

It is confusing for students regarding the two forms of the Fermat’s Little Theorem, which is the generalization of the ancient Chinese Remainder Theorem (中国剩馀定理) — the only theorem used in modern Computer Cryptography .

General: For any number a

$\boxed { a^p \equiv a \mod p, \forall a}$

We get,
$a^{p} - a \equiv 0 \mod p$
$a. (a^{(p-1)} -1) \equiv 0 \mod p$
$p \mid a.(a^{(p-1)} -1)$
If (a, p) co-prime, or g.c.d.(a, p)=1,
then p cannot divide a,
thus
$p \mid (a^{(p-1)} -1)$
$a^{(p-1)} -1 \equiv 0 \mod p$

Special: g.c.d. (a, p)=1

$\boxed {a^{(p-1)} \equiv 1 \mod p, \forall a \text { co-prime p}}$