Exercise 1583Number theory › CongruencesL1Added 3 Nov 2026

Fermat's little theorem and pseudoprimes

#Fermat#pseudoprime#compositeness

Statement

Show that $2^{340}\equiv1\pmod{341}$ , so $341$ satisfies Fermat's congruence for $a=2$ despite being composite.

Hint

$341=11\cdot31$ . Compute $2^{340}$ mod $11$ and mod $31$ .

Show solutionHide solution

Mod $11$ . $2^{10}\equiv1\pmod{11}$ , $340=34\cdot10$ , so $2^{340}\equiv1\pmod{11}$ .

Mod $31$ . $2^5=32\equiv1\pmod{31}$ , $340=68\cdot5$ , so $2^{340}\equiv1\pmod{31}$ .

CRT. By CRT, $2^{340}\equiv1\pmod{341}$ .

Conclusion. $341$ is a Fermat pseudoprime to base $2$ .