Solution

Suppose you know the following: $$2^{340} \equiv 1 \pmod{341} \quad \quad \textrm{and} \quad \quad 3^{340} \equiv 56 \pmod{341}$$ Can you immediately tell (without further calculation) if $341$ is prime or composite? Explain how.


$341$ must be composite, as Fermat's Little Theorem guarantees that if it were prime, and noting that $3 \not\equiv 0\pmod{341}$, then it would be the case that $3^{340} \equiv 1 \pmod{341}$.

Note, this theorem does not prohibit $2^{340} \equiv 1 \pmod{341}$ from occurring when the modulus is composite.