Exercise 847Number theory › CongruencesL1Added 3 Nov 2026

Fermat's little theorem

#Fermat#prime#modular exponentiation

Statement

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

Hint

For prime $p$ and $\gcd(a,p)=1$ : $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}$ .

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

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