Stelling van Euler

De stelling van Euler (ook wel Eulers totiëntstelling genoemd) is een bewering uit de elementaire getaltheorie, genoemd naar de Zwitserse wiskundige Leonhard Euler. De stelling van Euler is een generalisatie van de kleine stelling van Fermat, en is daardoor niet langer beperkt tot alleen priemgetallen. De stelling wordt op haar beurt zelf gegeneraliseerd door de stelling van Carmichael.

StellingBewerken

De stelling van Euler zegt dat als   en   positieve gehele getallen zijn waarvoor geldt dat ze relatief priem zijn (dat wil zeggen dat de grootste gemene deler van   en   gelijk is aan 1), dan geldt

 

waar   de indicator of totiënt van   is.

Voor   een priemgetal, volgt dan

 ,

en volgt de kleine stelling van Fermat onmiddellijk.

De stelling kan worden gebruikt om de berekening van hoge machten modulo   te vereenvoudigen. Ter illustratie beschrijven we de berekening van het laatste decimale cijfer van 7222, dat is 7222 (mod 10).

Er geldt dat 7 en 10 relatief priem zijn en   De stelling van Euler levert

 

op en we krijgen

 .

Globaal geldt dat men bij het reduceren van de macht van   modulo   (waarbij   en   relatief priem zijn) moet werken modulo   in de exponent van  . Dus

 ,

als

 .

BewijzenBewerken

Leonhard Euler publiceerde in 1736 een bewijs. Met moderne technieken kan de stelling als volgt bewezen worden: de getallen   die relatief priem zijn met   zijn de eenheden van de ring   en vormen een groep voor de vermenigvuldiging modulo  . Deze groep heeft   elementen en de stelling van Euler volgt dan uit de stelling van Lagrange.

Alternatief bewijs

Er is ook een direct bewijs. Als   een gereduceerd reststelsel is en   is relatief priem met  , betekent vermenigvuldigen van de elementen van   met   een permutatie, dus  . Dan volgt uit  , dat  . Omdat

 

volgt ook:

 

ToepassingBewerken

De stelling van Euler wordt onder meer gebruikt in de cryptografie, in het bijzonder RSA (cryptografie). Voor RSA-toepassing is slechts een speciaal geval van de stelling van Euler nodig, namelijk het geval dat  , waarin   en   verschillende priemgetallen zijn. In het geval van cryptografie zijn   en   zeer grote priemgetallen bestaande uit honderden cijfers.