De kleine stelling van Fermat

Als p een priemgetal is en a en p onderling ondeelbaar zijn dan geldt:

$a^{p-1} \equiv 1 \text{ mod } p$

Uit deze stelling, die de kleine stelling van Fermat genoemd wordt en in 1640 een eerste keer vermeld werd, volgt dat voor elke a en voor een priemgetal p geldt dat

$a^p \equiv a \text { mod } p$

De stelling wordt bijvoorbeeld gebruikt om de restklasse modulo een groot getal uit te rekenen. Bereken bijvoorbeeld de rest bij deling van $2^{245}$ door 11. Volgens de kleine stelling van Fermat is $2^{10} \equiv 1 \text{ mod } 11$ , dus is $2^{245} \equiv (2^{10})^24.2^5 \equiv 2^5 \equiv 10 \text{ mod } 11$ .

Er bestaat een veralgemening voor de stelling, die zegt dat als a en m onderling ondeelbaar zijn, geldt

$a^{\varphi(m)} \equiv 1 \text { mod }m$

Hierbij is $\varphi(m)$ de totiënt functie van Euler die het aantal getallen, kleiner dan m, berekent die onderling ondeelbaar zijn met m. Deze stelling wordt de Euler-Fermat stelling genoemd.