Kleine stelling van Fermat

De kleine stelling van Fermat zegt dat als p een priemgetal is, voor ieder geheel getal a geldt dat

$a^p \equiv a \pmod{p}\,\!$

Dit betekent dat als ik een willekeurig geheel getal a neem, het p maal met zichzelf vermenigvuldig, en er vervolgens a vanaf trek, het resultaat deelbaar is door p.

Een handig vervolg van de kleine stelling van Fermat is:

$a^{p-1} \equiv 1 \pmod{p}\,\!$

Deze vorm van de stelling is echter enkel geldig als a en p relatief priem zijn, of eenvoudiger (omdat p een priemgetal is): a geen veelvoud is van p. Dit komt doordat we beide leden van de eerste stelling moeten vermenigvuldigen met de inverse van $a\pmod{p}\,\!$ en deze bestaat niet als a een veelvoud is van p. Dit is eenvoudig in te zien: Als a een veelvoud is van p dan is $a\pmod{p}\ \equiv 0 \pmod{p}\,\!$. We zouden dus het inverse element moeten vinden van 0. Het inverse element van 0 zou een getal zijn waarvoor geldt dat als we het vermenigvuldigen met 0, we het eenheidselement $1\pmod{p}\,\!$ krijgen. Dit is uiteraard niet mogelijk.

Deze stelling wordt bijvoorbeeld gebruikt om modulo van een groot getal uit te rekenen.

Bewijs van de kleine stelling van Fermat

In dit bewijs gebruiken we de volgende notatie voor $a,p \in \Z$ en p een priemgetal:

• $a\mod{p}$ is de rest bij gehele deling van a door p
• $p | a$ "p deelt a"; dit wil zeggen dat $a\mod{p} = 0$, oftewel dat a een veelvoud is van p
• $p \not| a$ "p deelt a niet"; dit wil zeggen dat $a\mod{p} \not= 0$, oftewel dat a geen veelvoud is van p
• $a + k*p$ wil zeggen "a plus of min een veelvoud van p"

Om de kleine stelling te bewijzen, maken we gebruik van een hulpstelling:

• Zij $p\not| a$, dan $a*m = a*n \pmod{p} \Rightarrow m = n \pmod{p}$
  • Bewijs:

Stel $p\not| a$ en $a*m = a*n \pmod{p}$

Dan geldt dus $a*m - a*n = 0 \pmod{p}$, dus $a*(m-n) = 0 \pmod{p}$, dus $p | a(m-n)$.

We weten dat a geen veelvoud is van p. En p is priem(getal), dus p is ook geen veelvoud van a.

Dus moet gelden $m - n = 0 \pmod{p}$, oftewel het verschil tussen m en n is een veelvoud van p.

Oftewel m is n plus of min een veelvoud van p. Oftewel:

$m = n \pmod{p}$

Merk op dat uit de hulpstelling logisch volgt dat ook geldt:

• Indien$p\not| a$, dan $m \not= n \pmod{p} \Rightarrow a*m \not= a*n \pmod{p}$

Bewijs voor de kleine stelling:

• Zij p priem en $a\in\Z$; er zijn nu twee gevallen:

1. $p|a$: in dit geval is a een veelvoud van p en ieder veelvoud van a dus ook, dus triviaal geldt $a^{p} = a \pmod{p}$
2. $p\not|a$: Beschouw nu alle getallen $1,2,\ldots,p-1$.

Deze p-1 getallen delen allemaal p niet en zijn ongelijk aan p (dus ook modulo p).

Ook geldt, wegens $p\not|a$, dat het product van een van deze getallen met a, modulo p, weer gelijk aan een van deze getallen (dit volgt uit het feit dat p een priemgetal is; voor priemgetallen p geldt: als $p | ab$, dan $p | a \or p | b$; de omkering hiervan levert op dat $p \not| a \and p \not| b \Rightarrow p \not| ab \Rightarrow ab \not= 0 \pmod{p}$ $\Rightarrow ab \in \{1, 2, \ldots, p-1\} \pmod{p}$).

Daarnaast volgt uit de omkering van de hulpstelling dat voor $x, y \in \{1, 2, \ldots, p-1\}$ geldt dat $x \not= y \pmod{p} \Rightarrow a*x \not= a*y \pmod{p}$. Dit impliceert dat de getallen $a*1, a*2, \ldots, a*(p-1)$ modulo p een permutatie vormen van de getallen $1, 2, \ldots, p-1$. Hieruit volgt uiteindelijk dat de vermenigvuldiging $(1*a) * (2*a) * \ldots * ((p-1) * a)$ modulo p hetzelfde oplevert als $1 * 2 * \ldots * (p-1)$:

$1 * 2 * \ldots * (p-1) * a^{p-1} = 1 * 2 * \ldots * (p-1) \pmod{p}$

het zijn tenslotte al dezelfde getallen, met elkaar vermenigvuldigd (zij het niet in dezelfde volgorde).

Door onze hulpstelling volgt nu onmiddellijk: $a^{p-1} = 1 \pmod{p}$

Vermenigvuldig nu beide zijden met a: $a^{p} = a \pmod{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} = a \mod{k}$,

dan is niet noodzakelijkerwijs k een priemgetal.

Een getal q dat geen priemgetal is, maar waarvoor geldt dat

$a^{q} = a \mod{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} = a \mod{r}$

(voor zekere a) dan is r een priemgetal of een pseudo-priemgetal.

Er is bewezen dat er oneindig veel pseudo-priemgetallen bestaan. Echter, binnen de gehele getallen zijn de pseudo-priemgetallen wel 'dunner gezaaid' dan de priemgetallen.

Grote stelling van Fermat

De kleine stelling van Fermat mag niet worden verward met de Grote 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. Het theorema werd uiteindelijk bewezen door de Britse wiskundige Andrew Wiles in november 1994.