Loading AI tools
Van Wikipedia, de vrije encyclopedie
De stelling van Euler, ook wel Eulers totiëntstelling genoemd, is een bewering uit de elementaire getaltheorie, genoemd naar de wiskundige Leonhard Euler uit Zwitserland. De stelling van Euler is een generalisatie van de kleine stelling van Fermat en is daardoor niet langer tot alleen priemgetallen beperkt. De stelling wordt op haar beurt zelf gegeneraliseerd door de stelling van Carmichael.
De stelling van Euler zegt dat als en positieve gehele getallen zijn waarvoor geldt dat ze onderling ondeelbaar zijn, wat wil zeggen dat de grootste gemene deler van en gelijk is aan 1, dat 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 .
Er geldt dat 7 en 10 relatief priem zijn en .
volgens de stelling van Euler en
Er geldt dat
als
Leonhard Euler publiceerde in 1736 een bewijs.
Het bewijs kan worden gegeven door te stellen dat de getallen die relatief priem zijn met de eenheden van de ring zijn en een groep vormen voor de vermenigvuldiging modulo . Deze groep heeft elementen en de stelling van Euler volgt dan uit de stelling van Lagrange.
Als een gereduceerd reststelsel is en onderling ondeelbaar met is, betekent vermenigvuldigen van de elementen van met een permutatie, dus . Dan volgt uit , dat . Omdat
volgt ook:
De stelling van Euler wordt onder meer in de cryptografie gebruikt, in het bijzonder in het RSA-algoritme. Er is voor die toepassing maar een specifiek 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 die uit honderden cijfers bestaan.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.