Fermat’s Little Theorem can be used to prove a given number is not prime

Question

Present an argument using Fermat’s Little Theorem to show that $341$ is not a prime number.

How do we go about this? Would $a=7$ work?

Answer 1

Fermat's little theorem states that if $p$ is a prime number and $a$ is any natural number not divisible by $p$, then

$$ a^{p−1} \equiv 1\pmod{p} $$

Assuming $p = 341$ to be prime, we find this is not the case as

$$ 7^{341-1}=7^{340} \equiv 56 \pmod{341} $$

Hence, 341 is not a prime.

Answer 2

Just for fun, here's a proof using Fermat's other theorem, namely that primes congruent to $1$ mod $4$ are expressible as the sum of two squares, one of which is even and the other odd.

Since $341\equiv5$ mod $8$, the even square must be congruent to $4$ mod $8$ (odd squares being congruent to $1$ mod $8$). This leaves only a handful of possibilities. But

$$\begin{align} 341-2^2&=337\\ 341-6^2&=305\\ 341-10^2&=241\\ 341-14^2&=145\\ 341-18^2&=17 \end{align}$$

are all non-squares. So $341$ cannot be prime.