WisFaq!

Kleine stelling van Fermat

Ik begrijp de kleine stelling van Fermat niet. Ik heb de uitleg op de site al bekeken en ook die op www.pandd.demon.nl. Zou u hem vrij uitgebreid kunnen uitleggen, want ik weet bij de eerste stap (op pandd.demon.nl) al niet hoe ze aan de letters/getallen komen?

En kan je ook met mod werken op de gafische rekenmachine van Texas Instruments?

Alvast heel erg bedankt

Dilana
14-4-2002

Antwoord

De kleine stelling van Fermat beweert het volgende:

als p een priemgetal is en je kunt het getal a NIET delen door p, dan is a^p-1 - 1 deelbaar door p.

Men noteert dit als a^p-1=1(modp)

Ik neem aan dat je weet wat een priemgetal is: een getal (>1) dat alléén deelbaar is door zichzelf en door 1.
Priemgetallen zijn dus: 2, 3, 5, 7, 11, 13, 17.....
Men weet dat er oneindig veel priemgetallen zijn.

Laten we de kleine stelling van Fermat eens toepassen.

Neem als priemgetal bijvoorbeeld p = 7.
Nu moet er nog een ander getal a komen waar 7 niet deelbaar op is. Laten we a = 68 nemen, inderdaad niet deelbaar door 7.
Volgens de stelling zou nu moeten gelden dat 67⁶-1 deelbaar is door 7.
Natuurlijk zie je dat niet zo maar eventjes, maar als je het uitrekent, dan blijkt 67⁶-1 gelijk te zijn aan 9045832168 en dat kun je inderdaad precies delen door 7.
Resultaat van die deling: 12922626024.

Dit voorbeeld geeft natuurlijk direct het probleem weer: de getallen worden al snel zó groot, dat je eigenlijk niet meer als controle kunt narekenen of het klopt.
Via de techniek van het modulorekenen wordt echter veel van dat rekenwerk omzeild.

De kracht van de stelling is dan ook veel meer gelegen in het feit dat je wéét dat de deelbaarheid bestaat en het gaat in het algemeen helemaal niet om de uitkomst van die deling.
De stelling wordt o.a. ingezet bij het onderzoeken of een bepaald getal wel of niet een priemgetal is.

Wat het modulorekenen op de TI83 betreft: bij mijn weten zit die voorziening er niet in.

MBL
15-4-2002