AANSLUITINGSPROJECT TUE - VO
startpagina ] omhoog ]

 

Bewijs van de kleine stelling van Fermat

Het bewijs van de kleine stelling van Fermat is gebaseerd op de volgende hulpstelling.

Hulpstelling
Als p een priemgetal is en a een getal dat niet door p deelbaar is, dan geldt als a*i a*j (mod p) dan i j (mod p)

Controlevoorbeeld:
Bekijk het geval p = 7, a = 3. Als je de getallen 0, 1, 2, 3, 4, 5 en 6 met 3 vermenigvuldigt modulo 7 krijg je weer de getallen 0, 1, 2, 3, 4, 5 en 6.  Immers:
1*3 3 (mod 7)
2*3 6 (mod 7)
3*3 2 (mod 7)
4*3 5 (mod 7)
5*3 1 (mod 7)
6*3 4 (mod 7)

Je kunt dus alleen maar 3*i 3*j (mod 7) krijgen als i j (mod 7) .

Bewijs hulpstelling:
De bewering  a*i a*j (mod p) betekent dat a*i en a*j een p-voud verschillen. Met andere woorden p is een deler van a*i - a*j, dus p is een deler van a*(i-j). Maar p is priem en a is niet deelbaar door p. Dus geldt dat p een deler is van i - j Dit vertaalt zich weer in  i j (mod p)

Met deze hulpstelling kun je nu de kleine stelling van Fermat bewijzen. Voor het gemak "bewijzen" we de stelling van Fermat eerst voor het geval p = 7 en a = 3.

Bewijs kleine stelling Fermat
Beschouw de getallen 1, 2, 3, 4, 5, 6 (alleen de 0 ontbreekt) en vermenigvuldig ze alle met a, dus met 3. Je krijgt dan

1*3 3 (mod 7)
2*3 6 (mod 7)
3*3 2 (mod 7)
4*3 5 (mod 7)
5*3 1 (mod 7)
6*3 4 (mod 7)

Dat is het originele rijtje 1 , 2, 3, 4, 5 en 6 (maar in een andere volgorde). Dat moet ook op grond van de hulpstelling (ga na). Als twee verzamelingen getallen hetzelfde zijn (de volgorde doet er niet toe), moeten ook de producten van alle elementen erin gelijk zijn. De eerste verzameling bestond uit de getallen 1*3, 2*3, 3*3, 4*3, 5*3, 6*3 de tweede uit 1, 2, 3, 4, 5, 6 dus

(1*3)*(2*3)*(3*3)*( 4*3)*(5*3)*(6*3) 1*2*3*4*5*6 (mod 7)

Deel nu de gemeenschappelijke factoren aan beide kanten weg. Je krijgt dan 3*3*3*3*3*3 = 361 (mod 6).Dit is precies wat Fermat voorspelde. Het echte bewijs verloopt op dezelfde wijze. Er is in dit voorbeeld immers nergens echt gebruik gemaakt van de getallen p = 7 en a = 3. 

Het algemene geval:
Beschouw de getallen 1, 2, 3, 4, ... , p-1 en vermenigvuldig ze alle met a. Je krijgt dan 1*a  ,  2*a  ,  3*a  .......  en (p-1)*a. Volgens de hulpstelling zijn deze getallen (mod p) verschillend. Er geldt dan:

(1*a)*(2*a)*(3*a)*....*((p-1)*a) 1*2*3*4*....*(p-1) (mod p)

Deel links en rechts door 1*2*3....(p-1) dan volgt ap-11 (mod p).