Fermat's test to prove pseudoprimes

Question

I'm self teaching myself number theory as I'm doing a course in cryptography and anything I've found hasn't helped.

The question I'm stuck on is:

Use Fermat Test to show 19 is a pseudoprime base 3

Thank you for any help.

Answer 1

If 19 is a "pseudoprime" to base 3, that means $3^{18} \equiv 1 \pmod {19}$. Now, $3^{18} = 387420489$ and $$\frac{387420488}{19} = 20390552.$$ This confirms that 19 is a pseudoprime to base 3.

Now try it with $2^{18}$, $4^{18}, 5^{18}, 6^{18}, \ldots, 18^{18}$. As 19 is coprime to all these numbers from 2 to 18, we should find that $n^{18} \not\equiv 0 \pmod {19}$, however, in each case $1 \leq n < 19$, we find that $n^{18} \equiv 1 \pmod {19}$. Wait a minute... doesn't this mean that 19 is, I don't know, some kind of prime number?

It seems teachers frequently emphasize that a number passing the Fermat test to some base does not necessarily mean the number is prime. However, given your question, it seems that maybe they should also be emphasizing that prime numbers pass the test to any coprime base. Try $20^{18}, 21^{18}, 22^{18}$, etc.