# Number theory query

I'm trying to teach myself number theory as I'm doing a course in cryptography and am unsure how I can go about explaining why finding

$$2^{20} \bmod 21$$

shows that $21$ cannot be prime.

I'd appreciate any help which can be provided.

• The Little Fermat Theorem tells us that $2^{p-1}\equiv 1 \pmod p$ for all odd primes $p$, so if your expression isn't $1$ then... – lulu Mar 8 '17 at 17:39

$2^6\equiv 1\pmod{21}$ so indeed $2^{20}\equiv 4\cdot 2^{18}\equiv 4\not\equiv1\pmod{21}$.

On the other hand $a^{p-1}\equiv 1\pmod p$ for every prime $p$ and every integer $a$, provided that $p$ does not divide $a$.

Since $21$ does not divide $2$, we conclude that $21$ is not prime.

Here is a way to avoid Fermat's theorem:

$2^{6} \equiv 4 \equiv 2^2 \bmod 21$ implies $21$ divides $2^{20}-2^2=(2^{10}-2)(2^{10}+2)$.

However, $21$ doesn't divide either $2^{10}-2$ or $2^{10}+2$.

Therefore, $21$ cannot be prime.