# Kleine stelling van Fermat

De kleine stelling van Fermat zegt dat voor ieder priemgetal $p$ en ieder geheel getal $a$ geldt:
    $a^{p}\equiv a{\bmod {p}}$
De stelling is genoemd naar Pierre de Fermat (1601 of 1606/7 - 1665).
Als $a$ en $p$ onderling ondeelbaar zijn is de stelling equivalent met de uitspraak:
    $a^{p-1}\equiv 1{\bmod {p}}$
Als $a$ een veelvoud van $p$ is, geldt:
    $a^{p-1}\equiv 0{\bmod {p}}$
De stelling wordt bijvoorbeeld gebruikt om bij modulair rekenen de restklasse van een groot getal uit te rekenen en is in 1736 door Leonhard Euler bewezen.
Laat $a,p\in \mathbb {Z}$ zijn en $p$ een priemgetal.
    $a{\bmod {p}}$ is de rest bij geheeltallige deling van $a$ door $p$
Het bewijs van de kleine stelling maakt gebruik van een hulpstelling over modulair rekenen:
Voor $a{\bmod {p}}\neq 0$ geldt:
    $a\cdot m\equiv a\cdot n{\bmod {p}}\ \Longleftrightarrow \ m\equiv n{\bmod {p}}$
dus ook
    $a\cdot m\not \equiv a\cdot n{\bmod {p}}\ \Longleftrightarrow \ m\not \equiv n{\bmod {p}}$
Bewijs voor de kleine stelling:
Zij $p$ een priemgetal en $a\in \mathbb {Z}$. Er zijn twee mogelijkheden:
    Het spreekt in dit geval vanzelf dat $a^{p}\equiv a{\bmod {p}}$.
    Beschouw alle getallen $1,2,\ldots ,p-1$. Deze $p-1$ getallen zijn modulo $p$ ongelijk aan 0. Het product $ab$ van een van deze getallen $b$ met $a$ is modulo $p$ weer gelijk aan een van deze getallen.
    $a\not \equiv 0{\bmod {p}}$ en als $a\cdot b\equiv 0{\bmod {p}}$, dan $a{\bmod {p}}=0$ of $b{\bmod {p}}=0$. Het product $ab$ kan dus geen 0 zijn.
    Voor $x,y\in \{1,2,\ldots ,p-1\}$ geldt dat $x\not \equiv y{\bmod {p}}\Leftrightarrow a\cdot x\not \equiv a\cdot y{\bmod {p}}$. Dus vormen de getallen $a\cdot 1,a\cdot 2,\ldots ,a\cdot (p-1){\bmod {p}}$ een permutatie van de getallen $1,2,\ldots ,p-1$.
    Hieruit volgt voor de vermenigvuldiging met $a$ dat $(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 $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 $a^{p-1}\equiv 1{\bmod {p}}$ en door beide zijden met $a$ te vermenigvuldigen dat $a^{p}\equiv a{\bmod {p}}$.

## Pseudo-priemgetallen

Het omgekeerde van de kleine stelling van Fermat is niet algemeen geldig. Als voor zekere gehele $a$ en $k$ geldt dat
    $a^{k}\equiv a{\bmod {k}}$,
dan is $k$ niet noodzakelijk een priemgetal.
Een getal $q$ dat geen priemgetal is, maar waarvoor geldt dat
    $a^{q}\equiv a{\bmod {q}}$
voor zekere $a$ wordt een pseudopriemgetal genoemd. Als $q$ de eigenschap heeft dat het bovengenoemde geldt voor elke $a$, dan heet $q$ een carmichael-getal. Hierbij is de naam fermattest bedacht: als een getal $r$ voldoet aan
    $a^{r}\equiv a{\bmod {r}}$
voor zekere $a$ dan is $r$ een priemgetal of een pseudo-priemgetal.
Er is bewezen dat er oneindig veel pseudo-priemgetallen bestaan, maar binnen de gehele getallen zijn de pseudo-priemgetallen wel 'dunner gezaaid' dan de priemgetallen.

## Laatste stelling van Fermat

De kleine stelling van Fermat mag niet worden verward met de laatste stelling van Fermat, die zegt dat de vergelijking $x^{n}+y^{n}=z^{n}$ geen geheeltallige oplossing heeft verschillend van 0 voor alle gehele waarden van $n$ groter dan 2. De stelling werd in november 1994 bewezen door de Britse wiskundige Andrew Wiles.

## Literatuur

* M.C. van Hoorn, college over kleine stelling van Fermat aan de RUG