\require{AMSmath}

Kleine stelling van Fermat

Hallo,

Op school ben ik nu bezig met het onderwerp cryptologie. Tot nu toe gaat alles goed, alleen ben ik nu bij de kleine stelling van Fermat. Hier ondervind ik wat problemen. Zouden jullie mij hierbij kunnen helpen?
Met kleine getallen lukt het wel, bijvoorbeeld:
10⁶(mod 7) = 1 (mod 7) als het goed is.

Maar met de grotere getallen lukt het niet, bijvoorbeeld:
6¹²⁶ (mod 127)

Zou iemand mij hier mee kunnen helpen?

Alvast bedankt!

Axel
Leerling bovenbouw havo-vwo - dinsdag 17 februari 2009

Antwoord

De kleine stelling van Fermat zegt:
als n een priemgetal is dan geldt voor ieder positief geheel getal a dat geen gemeenschappelijke factoren heeft met n, dat a^n-1 (mod n)=1.
Nu is 127 een priemgetal dus 6¹²⁶(mod 127)=1.

Maar je bedoelt waarschijnlijk dat je dit met behulp van je rekenmachientje zou willen controleren.
De rekenregels voor machten gelden ook bij modulo rekenen.
Je kunt daarmee 6¹²⁶ opspslitsen:
Om te beginnen: 6¹²⁶=6⁶³·6⁶³
6⁶³=(6⁷)⁹
6⁷ mod 127=279936 mod 127=28, dus
(6⁷)⁹ mod 127=28⁹ mod 127
(28⁹) mod 127=(28³)³ mod 127=108³ mod 127=126.
Dus 6¹²⁶ mod 127=6⁶³·6⁶³ (mod 127)=(126·126) mod 127=15876 mod 127=1

hk
woensdag 18 februari 2009

©2001-2024 WisFaq