WisFaq!

Stelling van Euler en Euclidisch algoritme

Ik ben een vwo6 leerling en ben bezig met een po wiskunde over Cryptografie. Nu heb ik een redelijk goede uitleg van de (kleine) Stelling van Fermat en de Stelling van Euler en hun bewijzen (en bewijs hulpstelling) dat deze stellingen kloppen. Maar ik snap helaas deze stelling niet. Wel snap ik het Algoritme van Euclides, het bewijs hiervan snap ik echter ook niet. Ik hoop dat jullie me verder kunnen helpen en me een uitleg kunnen geven over het voorgenoemde. Bij voorbaat dank en met vriendelijke groet

karin
25-9-2003

Antwoord

Beste Karin,

De stelling van Euler waar je op doelt die luidt:

Als N een geheel getal groter dan 1 is, en a is een geheel getal zodat ggd(a,N)=1, dan geldt dat a^f(N)-1 deelbaar is door N.

Hier is f de Euler f-functie of Euler totient-functie (Dat totient kun je met name terugvinden in Engelstalige bronnen). Die functie doet het volgende: f(n) geeft het aantal getallen van 1 t/m n-1 dat een ggd gelijk aan 1 heeft met n.

Bijvoorbeeld: f(6) = 2, want alleen ggd(1,6) en ggd(5,6) zijn gelijk aan 1. De ggd's ggd(2,6)=ggd(4,6)=2 en ggd(3,6)=3 zijn allemaal ongelijk aan 1.

De stelling van Euler zegt nu dus bijvoorbeeld, aangezien ggd(13,6)=1, dat 13^f(6) - 1 = 13² - 1 deelbaar is door 6 (Controleer maar).

De kleine stelling van Fermat is een bijzonder geval van de stelling van Euler. De stelling van Fermat neemt voor N een priemgetal p. Het is eenvoudig te bedenken dat f(p) gelijk is aan p-1, omdat alle getallen van 1 t/m p-1 een ggd van 1 hebben met p. Priemgetallen hebben immers geen andere echte delers dan 1.

Dan het Euclidisch algoritme. Het bewijs daarvan is gebaseerd op het volgende:

• Stel dat t een deler is van u en van v. Dan is t ook een deler van u-v en v-u.
  
• Stel dat t een deler is van u en niet van v. Dan is t ook niet een deler van u-v noch van v-u.

Deze twee dingetjes zijn eenvoudig in te zien lijkt me. Maar dat betekent dus: als je begint met twee getallen, zeg

945 612

dan is de ggd van die getallen hetzelfde als die van

612 945-612 = 333

want de gemeenschappelijke delers van 945 en 612 zijn ook delers van 333, en een deler van 612 die geen deler was van 945 is dat ook niet van 333.

Het Euclidisch algoritme bestaat uit niets meer dan een handige herhaling van deze truc.

FvL
26-9-2003