Kleine stelling van Fermat

Laat ${\displaystyle a,p\in \mathbb {Z} }$ zijn en ${\displaystyle p}$ een priemgetal.

${\displaystyle a{\bmod {p}}}$ is de rest bij geheeltallige deling van ${\displaystyle a}$ door ${\displaystyle p}$

Het bewijs van de kleine stelling maakt gebruik van een hulpstelling over modulair rekenen:

Voor ${\displaystyle a{\bmod {p}}\neq 0}$ geldt:

${\displaystyle a\cdot m\equiv a\cdot n{\bmod {p}}\ \Longleftrightarrow \ m\equiv n{\bmod {p}}}$

dus ook

${\displaystyle a\cdot m\not \equiv a\cdot n{\bmod {p}}\ \Longleftrightarrow \ m\not \equiv n{\bmod {p}}}$

Bewijs voor de kleine stelling:

Zij ${\displaystyle p}$ een priemgetal en ${\displaystyle a\in \mathbb {Z} }$. Er zijn twee mogelijkheden:

• ${\displaystyle a{\bmod {p}}=0}$

Het spreekt in dit geval vanzelf dat ${\displaystyle a^{p}\equiv a{\bmod {p}}}$.

• ${\displaystyle a{\bmod {p}}\neq 0}$.

Beschouw alle getallen ${\displaystyle 1,2,\ldots ,p-1}$. Deze ${\displaystyle p-1}$ getallen zijn modulo ${\displaystyle p}$ ongelijk aan 0. Het product ${\displaystyle ab}$ van een van deze getallen ${\displaystyle b}$ met ${\displaystyle a}$ is modulo ${\displaystyle p}$ weer gelijk aan een van deze getallen.

${\displaystyle a\not \equiv 0{\bmod {p}}}$ en als ${\displaystyle a\cdot b\equiv 0{\bmod {p}}}$, dan ${\displaystyle a{\bmod {p}}=0}$ of ${\displaystyle b{\bmod {p}}=0}$. Het product ${\displaystyle ab}$ kan dus geen 0 zijn.

Voor ${\displaystyle x,y\in \{1,2,\ldots ,p-1\}}$ geldt dat ${\displaystyle x\not \equiv y{\bmod {p}}\Leftrightarrow a\cdot x\not \equiv a\cdot y{\bmod {p}}}$. Dus vormen de getallen ${\displaystyle a\cdot 1,a\cdot 2,\ldots ,a\cdot (p-1){\bmod {p}}}$ een permutatie van de getallen ${\displaystyle 1,2,\ldots ,p-1}$.

Hieruit volgt voor de vermenigvuldiging met ${\displaystyle a}$ dat ${\displaystyle (1\cdot a)\cdot (2\cdot a)\cdot \ldots \cdot ((p-1)\cdot a){\bmod {p}}=1\cdot 2\cdot \ldots \cdot (p-1)}$, dus is ${\displaystyle 1\cdot 2\cdot \ldots \cdot (p-1)\cdot a^{p-1}\equiv 1\cdot 2\cdot \ldots \cdot (p-1){\bmod {p}}}$.

Daaruit volgt dat ${\displaystyle a^{p-1}\equiv 1{\bmod {p}}}$ en door beide zijden met ${\displaystyle a}$ te vermenigvuldigen dat ${\displaystyle a^{p}\equiv a{\bmod {p}}}$.