kleine stelling van Fermat

© h.hofstede (h.hofstede@hogeland.nl)

De kleine stelling van Fermat.

Als p een priemgetal is, dat niet in de ontbinding van a voorkomt, dan geldt:

a^p^{- 1} ☰ 1 (mod p)

Bewijs.

Bekijk de rij a, 2a, 3a, ..., (p - 1)a
Twee getallen uit die rij zijn nooit aan elkaar gelijk (mod p)
Immers als ma = na (mod p) dan is (m - n)a = 0 (mod p) en omdat p geen deler is van a zou p dan een deler zijn van (m - n). Maar dat kan niet, want p > (m - n).

Dus zijn alle resten van die getallen modulo p ongelijk aan elkaar.
Die resten zijn dus (op volgorde gezet) precies de getallen 1, 2, 3, ..., (p - 1)
Als je nu al die getallen met elkaar vermenigvuldigt, dan krijg je:
a • 2a • 3a • ... • (p - 1)a = a^{p - 1} • (p - 1)!

Maar als je alle resten vermenigvuldigt dan krijg je (p - 1)!
Dus moet gelden a^{p - 1} • (p - 1)! ☰ (p - 1)! (mod p)
Daaruit volgt direct de stelling.

q.e.d.

De kleine stelling van Fermat maakt het mogelijk om snel en efficiënt machten modulo p te bepalen.
Stel bijvoorbeeld dat je wilt weten hoe groot 3²⁰¹ mod 11 is.
Fermat geeft 3¹⁰ ☰ 1 (mod 11), want 11 komt niet voor in de ontbinding van 3
3²⁰⁰ = (3¹⁰)²⁰ = 1²⁰= 1
3²⁰¹ = 3²⁰⁰ • 3 = 1 • 3 = 3

Een direct gevolg van de kleine stelling van Fermat zie je als je beide kanten met a vermenigvuldigt:

a^p☰ a (mod p)

Orde.

Het kleinste gehele getal n > 0 waarvoor geldt dat aⁿ ☰ 1 (mod b) noemen we de "orde van a modulo b".
We noteren dat voortaan als n = ord_b(a).
Wanneer bestaat er eigenlijk een orde? Dat zegt de volgende stelling:

a heeft een orde modulo b ⇔ ggd(a, b) = 1

Bewijs.

⇒

Als a orde b heeft, dan bestaat er dus een getal n zodat aⁿ ☰ 1 (mod b)
Maar aⁿ (mod b) ☰ (a (mod b)ⁿ en als dat 1 (mod b) is, dan is ook a (mod b) ☰ 1

⇐

Als ggd(a, b) = 1

q.e.d.

Een gevolg daarvan is, dat als n = ord_b(a) dan is a^k ☰ a^{k + n} , en n is het kleinste getal waarvoor dit geldt.
In dat geval is de rij van alle resten van a^k (mod b) periodiek met periode n.
Bekijk bijvoorbeeld de resten bij b = 13 en a = 5 :
5¹ , 5², 5³ , 5⁴ , 5⁵, 5⁶, 5⁷, 5⁸, ....
geeft 5, 12, 8, 1, 5, 12, 8, 1, ... en die is periodiek met periode ord₁₃(5) = 4
(Bij die eerste 1 in de rij hadden we natuurlijk direct kunnen stoppen, immers als 5⁴ (mod 13) ☰ 1 dan is 5⁵ ☰ 5⁴ • 5 ☰ 1 • 5 = 5, en dan is 5⁶ ☰ 5², 5⁷ ☰ 5³ enz.)
Hé grappig; dan kun je nu je weet dat de orde 4 is, ook op een andere manier de inverse van 5 (mod 13) berekenen:
5^-1 ☰ 5^{-1 + 4} ☰ 5³ ☰ 8 en inderdaad is 8 • 5 ☰ 40 ☰ 1

De vergelijking a^m = 1 (mod b) geldt dus alleen als ord_b(a) een deler is van m, immers op die plaatsen kwamen de enen in het rijtje met resten.
En a^m = aⁿ (mod b) kan dus om dezelfde reden alleen als m = n (mod b).
Dat heeft het volgende gevolg:

als ggd(ord_n(a), ord_n(b)) = 1 dan geldt:

ord_n(ab) = ord_n(a) • ord_n(b)

Deze beschouwingen over de orde kunnen we natuurlijk mooi combineren met de kleine stelling van Fermat:

Voor elk priemgetal p geldt dat ord_p(a) een deler is van (p - 1)

Immers Fermat zegt dat a^{p - 1} ☰ 1 (mod p) en hierboven zagen we dat a^m = 1 (mod p) alleen geldt als ord_p(a) een deler is van m.

Stelling van Euler.

't Is natuurlijk een beetje jammer dat de kleine stelling van Fermat alleen maar geldt voor priemgetallen. De stelling van Euler geeft een soortgelijke eigenschap voor samengestelde getallen.
Komt 'íe:

Als ggd(a, b) = 1 dan geldt:

a^φ(b) = 1 (mod b)

Uiteraard weer voor gehele a en b en b > 0.

Die φ is de totiëntfunctie uit deze les. Snel gezegd: het aantal getallen onder b dat geen priemfactor met b gemeenschappelijk heeft.

Ik hoop dat je ziet dat deze stelling eigenlijk een uitbreiding van de kleine stelling van Fermat is: neem voor b een priemgetal dan geldt φ(b) = b - 1, immers alle getallen onder b zijn dan copriem met b, en dan staat er gewoon de kleine stelling van Fermat.

Uit deze stelling volgt dan direct weer dat ord_b(a) een deler is van φ(b).