Kleine stelling van Fermat

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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}\,\!

De stelling is genoemd naar Fermat (1601 of 1606/7 - 1665).

Een handig vervolg van de kleine stelling van Fermat is:

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


Deze vorm van de stelling is echter alleen geldig als a en p relatief priem zijn. Wanneer is gegeven dat p een priemgetal is, mag a geen veelvoud van p zijn. Dit komt doordat we beide leden van de eerste stelling moeten vermenigvuldigen met de inverse van a en deze bestaat niet als a een veelvoud van p is.

De stelling wordt bijvoorbeeld gebruikt om restklasse modulo een groot getal uit te rekenen.

Bewijs van de kleine stelling van Fermat[bewerken]

a,p \in \Z en p is een priemgetal.

  • a\mod{p} is de rest bij geheeltallige 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).
a is geen veelvoud is van p en p is een priemgetal, 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.
m = n \pmod{p}

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

  • Indienp\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[bewerken]

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.

Laatste stelling van Fermat[bewerken]

1rightarrow blue.svg Zie Laatste stelling van Fermat voor het hoofdartikel over dit onderwerp.

De kleine stelling van Fermat mag niet worden verward met de laatste stelling van Fermat, 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.

Externe bron[bewerken]