Kleine stelling van Fermat

Van Wikipedia

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.

[bewerk] 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 , dan
- Bewijs:

Stel $p\not| a$ en

a * m = a * n (mod p)

Dan geldt dus

a * m - a * n = 0(mod p)

, dus

a * (m - n) = 0(mod 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(mod 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 (mod 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:

$p | a$ : in dit geval is a een veelvoud van p en ieder veelvoud van a dus ook, dus triviaal geldt $a p = a (mod p)$
$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 | a b

, 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(mod p)

Vermenigvuldig nu beide zijden met a:

a p = a (mod p)

[bewerk] 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 'pseudo-priemgetal' genoemd. Als q de eigenschap heeft dat het bovengenoemde geldt voor willekeurige a, dan heet q een 'Carmichael getal'.

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.

[bewerk] 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.

Categorieën: Getaltheorie | Discrete wiskunde | Wiskundige stelling

Kleine stelling van Fermat

Van Wikipedia

[bewerk] Bewijs van de kleine stelling van Fermat

[bewerk] Pseudo-priemgetallen

[bewerk] Grote stelling van Fermat

Views

Navigatie

Informatie

Zoeken

in andere talen