De kleine stelling van Fermat zegt dat voor ieder priemgetal
en ieder geheel getal
geldt:
![{\displaystyle a^{p}\equiv a{\bmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f778ab66d9ff1e3609ac03c6bc89ce48f6947fe1)
De stelling is genoemd naar Pierre de Fermat (1601 of 1606/7 - 1665).
Als
en
onderling ondeelbaar zijn is de stelling equivalent met de uitspraak:
![{\displaystyle a^{p-1}\equiv 1{\bmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/112bd3e75db3f8d394dc3b430bcf7cc32aa64e95)
Als
een veelvoud van
is, geldt:
![{\displaystyle a^{p-1}\equiv 0{\bmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f3a5cb897c9250365b67a248d4708b49e00d53cb)
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.
Bewijs van de kleine stelling van Fermat
Laat
zijn en
een priemgetal.
is de rest bij geheeltallige deling van
door ![{\displaystyle p}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
Het bewijs van de kleine stelling maakt gebruik van een hulpstelling over modulair rekenen:
Voor
geldt:
![{\displaystyle a\cdot m\equiv a\cdot n{\bmod {p}}\ \Longleftrightarrow \ m\equiv n{\bmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ace2a4d1875cc018e02e745ade20979bdeeb5986)
dus ook
![{\displaystyle a\cdot m\not \equiv a\cdot n{\bmod {p}}\ \Longleftrightarrow \ m\not \equiv n{\bmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/708cf3c2929a8547e4cf8735a020bdfe9cbfc4d3)
Bewijs voor de kleine stelling:
Zij
een priemgetal en
. Er zijn twee mogelijkheden:
![{\displaystyle a{\bmod {p}}=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c78075e462448dd8497a7e739b0242e91c14ab1)
- Het spreekt in dit geval vanzelf dat
.
.
- Beschouw alle getallen
. Deze
getallen zijn modulo
ongelijk aan 0. Het product
van een van deze getallen
met
is modulo
weer gelijk aan een van deze getallen.
en als
, dan
of
. Het product
kan dus geen 0 zijn. - Voor
geldt dat
. Dus vormen de getallen
een permutatie van de getallen
. - Hieruit volgt voor de vermenigvuldiging met
dat
, dus is
. - Daaruit volgt dat
en door beide zijden met
te vermenigvuldigen dat
.
Pseudo-priemgetallen
Het omgekeerde van de kleine stelling van Fermat is niet algemeen geldig. Als voor zekere gehele
en
geldt dat
,
dan is
niet noodzakelijk een priemgetal.
Een getal
dat geen priemgetal is, maar waarvoor geldt dat
![{\displaystyle a^{q}\equiv a{\bmod {q}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e81f117da60e46493dc8831e8929d2d471980c2b)
voor zekere
wordt een pseudopriemgetal genoemd. Als
de eigenschap heeft dat het bovengenoemde geldt voor elke
, dan heet
een carmichael-getal. Hierbij is de naam fermattest bedacht: als een getal
voldoet aan
![{\displaystyle a^{r}\equiv a{\bmod {r}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e689db0b4efdd08529824fcbacf14dc3d9a30056)
voor zekere
dan is
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
geen geheeltallige oplossing heeft verschillend van 0 voor alle gehele waarden van
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