Originally Posted by

**Bacterius** Generally,

$\displaystyle \Rightarrow$ if $\displaystyle p$ is prime, then $\displaystyle a^{p - 1} \equiv 1 \pmod{p}$ for any $\displaystyle a$ such as $\displaystyle \gcd{(a, p)} = 1$.

$\displaystyle \Rightarrow$ if $\displaystyle a^{p - 1} \equiv 1 \pmod{p}$ for any $\displaystyle a$ such as $\displaystyle \gcd{(a, p)} = 1$, then $\displaystyle p$ is *likely* to be prime (Carmichael numbers are the only numbers that do not satisfy the statement, they are relatively rare but their existence invalidates the statement).