Brontekst bekijken van Kleine stelling van Fermat

De '''kleine stelling van Fermat''' zegt dat voor ieder [[priemgetal]] <math>p</math> en ieder [[geheel getal]] <math>a</math> geldt:
: <math>a^p \equiv a \bmod{p}</math>

De [[Stelling (wiskunde)|stelling]] is genoemd naar [[Pierre de Fermat]] ([[1601]] of [[1606]]/[[1607|7]] - 1665).

Als <math>a</math> en <math>p</math> [[Relatief priem|onderling ondeelbaar]] zijn is  de stelling equivalent met de uitspraak:
: <math>a^{p-1} \equiv 1 \bmod{p}</math>

Als <math>a</math> een [[Veelvoud (wiskunde)|veelvoud]] van <math>p</math> is, geldt:
: <math>a^{p-1} \equiv 0 \bmod{p}</math> 

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.

{{Uitklappen
| achtergrond = #efdfef
| titel = Bewijs van de kleine stelling van Fermat
| afb = 
| align = left
| tekstgrootte= 90%
| inhoud =

Laat <math>a,p \in \Z</math> zijn en <math>p</math> een priemgetal.

: <math>a \bmod p</math> is de rest bij [[geheeltallige deling]] van <math>a</math> door <math>p</math>

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

Voor <math>a \bmod p \neq 0</math> geldt: 
: <math>a \cdot m \equiv a \cdot n \bmod{p} \ \Longleftrightarrow \ m \equiv n \bmod{p}</math>

dus ook
: <math>a \cdot m \not \equiv a\cdot n \bmod{p}\ \Longleftrightarrow \ m \not \equiv n \bmod{p}</math>

Bewijs voor de kleine stelling:

Zij <math>p</math> een priemgetal en <math>a\in\Z</math>. Er zijn twee mogelijkheden:
* <math>a \bmod p = 0</math>
: Het spreekt in dit geval vanzelf dat <math>a^p \equiv a \bmod{p}</math>.
* <math>a \bmod p \neq 0</math>.
: Beschouw alle getallen <math>1, 2, \ldots, p-1</math>. Deze <math>p-1</math> getallen zijn modulo <math>p</math> ongelijk aan 0. Het product <math>ab</math> van een van deze getallen <math>b</math> met <math>a</math> is modulo <math>p</math> weer gelijk aan een van deze getallen.
: <math>a \not\equiv 0 \bmod{p} </math> en als <math>a \cdot b \equiv 0 \bmod{p}</math>, dan <math>a \bmod p = 0</math> of <math>b \bmod p = 0</math>. Het product <math>ab</math> kan dus geen 0 zijn.
: Voor <math>x, y \in \{1, 2, \ldots, p-1\}</math> geldt dat <math>x \not\equiv y \bmod{p} \Leftrightarrow a\cdot x \not \equiv a \cdot y \bmod{p}</math>. Dus vormen de getallen <math>a \cdot 1, a \cdot 2, \ldots, a \cdot (p-1) \bmod{p}</math> een [[permutatie]] van de getallen <math>1, 2, \ldots, p-1</math>.
: Hieruit volgt voor de vermenigvuldiging met <math>a</math> dat <math>(1 \cdot a) \cdot (2\cdot a) \cdot \ldots \cdot ((p-1) \cdot  a) \bmod{p} = 1 \cdot 2 \cdot \ldots \cdot (p-1)</math>, dus is <math>1 \cdot 2 \cdot \ldots \cdot (p-1) \cdot a^{p-1} \equiv 1 \cdot  2 \cdot  \ldots \cdot (p-1) \bmod{p}</math>.
: Daaruit volgt dat <math>a^{p-1} \equiv 1 \bmod{p}</math> en door beide zijden met <math>a</math> te vermenigvuldigen dat <math>a^p \equiv a \bmod{p}</math>.
}}

== Pseudo-priemgetallen ==
Het omgekeerde van de kleine stelling van Fermat is niet algemeen geldig.
Als voor zekere gehele <math>a</math> en <math>k</math> geldt dat
: <math>a^k \equiv a \bmod{k}</math>,
dan is <math>k</math> niet noodzakelijk een priemgetal.

Een getal <math>q</math> dat geen priemgetal is, maar waarvoor geldt dat
: <math>a^q \equiv a \bmod{q}</math>
voor zekere <math>a</math> wordt een pseudopriemgetal genoemd. Als <math>q</math> de eigenschap heeft dat het bovengenoemde geldt voor elke <math>a</math>, dan heet <math>q</math> een [[carmichael-getal]]. Hierbij is de naam [[Priemtest van Fermat|fermattest]] bedacht: als een getal <math>r</math> voldoet aan
: <math>a^r \equiv a \bmod{r}</math>
voor zekere <math>a</math> dan is <math>r</math> 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 ==
{{Zie hoofdartikel|Laatste stelling van Fermat}}

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

== Literatuur ==
* {{aut|M.C. van Hoorn}}, [https://www.math.rug.nl/~broer/pdf/ksFermat.pdf college over kleine stelling van Fermat] aan de [[Rijksuniversiteit Groningen|RUG]]

[[Categorie:Discrete wiskunde]]
[[Categorie:Modulair rekenen]]
[[Categorie:Wiskundige stelling|Fermat]]