Maths WorkshopMaths problems with full solutions
Exercise 1834Number theory › PrimesL1Added 3 Nov 2026

Fermat test detects compositeness

#Fermat test#witness#compositeness

Statement

Use the Fermat test to show 2121 is composite.

Hint

Try a=2a=2: if 220≢1(mod21)2^{20}\not\equiv1\pmod{21}, then 2121 is composite.

Show solutionHide solution

Solution

Compute. 26=64≡1(mod21)2^6=64\equiv1\pmod{21} (since 64−21⋅3=164-21\cdot3=1). So 220=218⋅22=(26)3⋅4≡4(mod21)≠12^{20}=2^{18}\cdot2^2=(2^6)^3\cdot4\equiv4\pmod{21}\neq1.

Conclusion. 220≢1(mod21)2^{20}\not\equiv1\pmod{21}, so 2121 is composite.

Remark. This is the Fermat primality test: if an−1≢1(modn)a^{n-1}\not\equiv1\pmod n for some aa coprime to nn, then nn is definitely composite.