Exercise 1129Number theory › PrimesL1Added 3 Nov 2026

Fermat's little theorem

#Fermat#prime#modular exponentiation

Statement

State Fermat's little theorem and compute $2^{100}\pmod{13}$ .

Hint

For prime $p$ and $p\nmid a$ : $a^{p-1}\equiv1\pmod p$ .

Show solutionHide solution

Theorem. If $p$ is prime and $p\nmid a$ , then $a^{p-1}\equiv1\pmod p$ .

Application. $p=13$ , $a=2$ , $p-1=12$ . So $2^{12}\equiv1\pmod{13}$ .

Reduce. $100=8\cdot12+4$ , so $2^{100}=(2^{12})^8\cdot2^4\equiv2^4=16\equiv3\pmod{13}$ .

Conclusion. $2^{100}\equiv3\pmod{13}$ .