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.
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ 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... $\endgroup$ – lulu Mar 8 '17 at 17:39
Add a comment
|
$\begingroup$
$\endgroup$
$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.
$\begingroup$
$\endgroup$
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.
