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.
Stelling
[bewerken | brontekst bewerken]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
- .
Bewijzen
[bewerken | brontekst bewerken]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:
Toepassing
[bewerken | brontekst bewerken]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.