De kleine stelling van Fermat

Introductie

Dit wiskunde onderzoek gaat over Pierre de Fermat, een wiskundige uit de 17e eeuw, en zijn stellingen. Fermat heeft geprobeerd al bestaande kennis toe te passen. Priemgetallen in de kleine stelling en Pythagoras’ stelling in de laatste stelling van Fermat. Dit maakt Fermat alleen nog maar interessanter. Fermat komt uit Frankrijk, een land dat een heel andere geschiedenis doormaakte dan Nederland. Dit onderzoek legt de kleine stelling van Fermat uit.

Hoe werkt de stelling?

De kleine stelling van Fermat luidt als volgt:

• a^p = a (mod p)

a is hier een volledig getal, zonder iets na de komma, a˃0. p staat hier voor een Priemgetal.

Hier volgt een korte uitleg van een priemgetal:

Een priemgetal is een getal dat alleen deelbaar is door het getal zelf, of door 1. Zo zie je dat 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 enzovoort priemgetallen zijn. Neem het priemgetal ‘7’. Deze is niet deelbaar door 2, 3, 4, 5, en evenals niet door 6. 7 is echter wel deelbaar door 7 (zichzelf) en door 1.

Klokrekenen

Om de stelling te begrijpen kan je eerst beginnen met klokrekenen: wat met modulo rekenen te maken heeft. Als het 18.00 uur is noem je dit ook wel ‘6 uur’. Het zijn telkens stappen van 12 uur.

Als het 10.00 uur is wanneer je naar school gaat, en wanneer het 16.00 uur is wanneer je klaar bent met school bereken je het zo: 10 + 6 = 4 (mod 12) 16.00 uur noem je ook wel ‘4 uur’. = 16 – 12 = 4 Nog een voorbeeld. 8 (mod 3) = 2 = 8 – 2 . 3= 2 Of

19 (mod 5) = 4 = 19 – 3 . 5 = 4

Of

11 (mod 2) = 1 = 11 – 5 . 2 = 1

Je moet het vermenigvuldigen met de module, en proberen er het meeste uit te halen. Bij het laatste voorbeeld kan ‘2 maal 5’ niet. Dit is 10. 3 maal 5 is 15, en dit past ook nog in de 19. 4 maal 5 is weer te veel, dit is 20. Wat overblijft is het antwoord.

Kleine stelling van Fermat

Dan kan je een stapje verder gaan: de kleine stelling van Fermat toepassen. Voorbeeld 1: a= 2 p= 7

Vul deze informatie in Dus: 2⁷= 2 (mod 7) De uitkomst hoort 2 te zijn. 2⁷= 128 128 / 7 ≈ 18 (zo weet je hoeveel er maximaal in hele getallen in past ) 128 – 18 . 7= 2 Het antwoord is inderdaad 2, dus dit voorbeeld klopt. Voorbeeld 2: a = 5 p = 13 Ook hier is P weer een priemgetal. 13 is namelijk alleen deelbaar door zichzelf en door 1.

Weer moet deze informatie in worden gevuld.

5 ¹³ = 5 (mod 13) De uitkomst hoort 5 te zijn 5¹³ = 1220703125 1220703125 / 13 ≈ 93900240 1220703125 – 93900240 . 13 = 5

De uitkomst is inderdaad 5, dus dit is weer een klein bewijs dat de formule klopt. Het gaat niet om het getal zelf, maar dat hij wil. Dus als je deze stappen volgt, niet op een komma getal uit komt.

Voorbeeld 3: a= 3 p = 17

3¹⁷ = 3 (mod 17) De uitkomst hoort 3 te zijn. Dit zal nu worden uitgerekend door de module toe te passen. 3¹⁷ = 129140163 129140163 / 17 ≈ 7596480 129140163 – 7596480 . 17 = 3

De uitkomst is inderdaad 3, dus het klopt.

Vervolg kleine stelling van Fermat

Dan heb je ook nog het vervolg op de kleine stelling van Fermat. Deze gaat als volgt: a^p-1=1 (mod p) Als we van deze formule zouden uitgaan, dan zou het antwoord altijd 1 moeten zijn. Net zoals met de vorige formule is a een heel getal en groter dan 0. p is ook hier een priemgetal. Zie vorige pagina voor een discrete uitleg van een priemgetal.

Hier het eerste voorbeeld, met dezelfde a en p als het eerste voorbeeld van de eerdere formule. Dus a = 2 p = 7

Deze worden ingevuld in a^p-1=1 (mod p) 2⁶ = 1 (mod 7) De uitkomst hoort altijd 1 te zijn. Met de modulo rekenen gaat het exact hetzelfde als de voorgaande. 2⁶ = 64 64 / 7 ≈ 9 64 – 9 . 7 = 1 Deze uitkomst is goed, namelijk 1.

Voorbeeld 2: a= 3 p= 19

3¹⁸=1 (mod 19) 3¹⁸ = 387420489 387420489 / 19 ≈ 20390552 38740489 – 20390552 . 19 = 1

Ook hier is het antwoord weer 1. Zo kan je zien dat 19 een priemgetal is, omdat deze formule klopt bij dit priemgetal. Dit allemaal kan alleen als a niet deelbaar is door p

Bewijs van de stelling

Ga vanuit dat a is niet deelbaar door p. Neem weer a=2 p=7 Dan is het idee dat je a met allemaal cijfers ervoor opschrijft. a, 2a, 3a, 4a, 5a, 6a, (p-1)a (want 7-1 = 6, en tot zover moet je het vermenigvuldigen met a) Dan moet je de getallen vermenigvuldigen met elkaar. Dus: a . 2a . 3a . 4a . 5a . 6a . (p-1) a Wat er in de formule zo uit ziet: a . 2a . 3a . 4a . 5a . 6a . (p-1) a = 1 . 2 . 3 . 4 . 5 . 6 . (p-1) (mod p) Als je het samenvoegt krijg je deze volgende formule . De a termen zijn in elkaar gevoegt.

Het uitroepteken na ‘(p-1)!’ staat voor faculteit, vermenigvuldigen vanaf het begin getal, in dit geval p=7 dus (7-1)=6 tot aan 1. In feite, aangezien aan beide kanten hetzelfde staat, kan je (p-1)! weglaten waardoor het deze formule wordt:

Het is de formule die we gebruikten. Maar om dit bewijs echt een bewijs te laten worden komt hier een voorbeeld: Nog steeds a=2 p=7 Vervolgens is dit de gebruikte volgorde, die telkens +2 doet. 2, 4, 6, 8, 10, 12 Deze gaat tot de 6, omdat (p-1), en p=7, dus (7-1)=6 Als je modulo 7 toepast wordt het het volgende. (Gebruik methode die eerder is uitgelegd) 2, 4, 6, 1, 3, 5 Als je deze sorteert wordt het 1, 2, 3, 4, 5, 6 Vervolgens vermenigvuldig je ze, wat maakt: 2 . 4 . 6 . 8 . 10 . 12 = 2 . 4 . 6 . 1 . 3 . 5 = 1 . 2 . 3 . 4 . 5 . 6 (mod 7) Wat word.. 3⁶(1 . 2 . 3 . 4 . 5 . 6) = (1 . 2 . 3 . 4 . 5 . 6) (mod 7) Omdat (1 . 2 . 3 . 4 . 5 . 6) aan beide kanten van de = zitten, kunnen deze weggelaten worden. Daarom wordt het 3⁶ = 1 (mod 7) Deze formule wordt gecontroleerd, of deze daadwerkelijk klopt. 3⁶ = 729 729 / 7 ≈ 104 729 – 104 . 7 = 1 De uitkomst hoort 1 te zijn, dus het bewijs klopt!

Hoe wordt de stelling gebruikt?

De kleine stelling van Fermat wordt gebruikt in cryptologie. Het wordt gebruikt om priemgetallen op te sporen. Wanneer een priemgetal verbazingwekkend groot is, is dit lastig om te berekenen. Met de kleine stelling van Fermat kan men het mogelijke priemgetal invullen in de formule. Als deze klopt, is het mogelijke priemgetal een zekerheid geworden.

Conclusie

De kleine stelling van Fermat is een van de belangrijkste stellingen van Pierre de Fermat, naast de laatste stelling van Fermat. De kleine stelling van Fermat is werkelijk bewezen. Deze is uitgelegd bij de deelvraag ‘Wat is het bewijs van de stelling’. Om de kleine stelling van Fermat te snappen moet je eerst leren wat klokrekenen is. Bij klokrekenen krijg je te maken met modulo rekenen, wat gebruikt wordt in de stelling. Als je dit onder de knie hebt kan je een stapje verder gaan. Hier gebruik je de formule. Wanneer je bij deze stap bent pas je het modulo rekenen toe.

Dan heb je het vervolg op de kleine stelling. Deze werkt in principe hetzelfde, alleen wordt ze iets anders geformuleerd. Maar dan moet deze stelling ook bewezen worden.

Je begint met modulo rekenen, en langzaamaan vul je de formule erbij. Op een logische wijze kom je uit bij de kleine stelling. Deze moet uitgerekend worden. Wanneer deze klopt weet je dat de stelling echt klopt. De kleine stelling wordt gebruikt om priemgetallen te herkennen. Als je een priemgetal hebt, waarvan je zeker wilt weten dat het een priemgetal is, vul je hem in in de formule. Als dit een geheel getal is, weet je dat het getal een priemgetal is.