Stelling van Euler
De Stelling van Euler (ook wel Eulers totienttheorema genoemd) is een bewering uit de elementaire getaltheorie, vernoemd 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 zijn beurt zelf gegeneraliseerd door de stelling van Carmichael.
De stelling van Euler zegt dat als a en n positieve gehele getallen zijn waarvoor geldt dat ze relatief priem zijn (ofwel GGD(a,n) = 1), dan geldt
- aφ(n) ≡ 1 (mod n),
waar φ(n) de indicator of totientfunctie is.
De stelling kan worden gebruikt om de berekening van hoge machten modulus n te vereenvoudigen. Ter illustratie beschrijven we de berekening van het laatste decimale cijfer van 7222, dat is 7222 (mod 10). Merk op dat 7 en 10 relatief priem zijn en φ(10) = 4. De stelling van Euler levert 74 ≡ 1 (mod 10) op en we krijgen 7222 ≡ 74·55 + 2 ≡ (74)55·72 ≡ 155·72 ≡ 49 ≡ 9 (mod 10).
Globaal geldt dat men bij het reduceren van de macht van a modulus n (waarbij a en n relatief priem zijn) moet werken met modulus φ(n) in het exponent van a: als x ≡ y (mod φ(n)), dan ax ≡ ay (mod n).
Indien we veronderstellen dat n=p een priemgetal is, dan hebben we φ(p)=p-1, en volgt de kleine stelling van Fermat onmiddellijk.
[bewerk] Bewijzen
Leonhard Euler publiceerde een bewijs in 1736. Met moderne technieken kan de stelling als volgt bewezen worden: de getallen a die relatief priem zijn met n vormen een groep bij een vermenigvuldiging mod n, de groep eenheden van de ring Z/nZ. Deze groep heeft φ(n) elementen en de Stelling van Euler volgt dan uit de Stelling van Lagrange.
Een ander bewijs: als a relatief priem is met n, dan zal vermenigvuldiging met a de rest veranderen met mod n, relatief priem met n; in andere woorden (waarbij we R nemen voor de reeks die bestaat uit φ(n) verschillende klassen) de reeksen { x : x in R } en { ax : x in R } zijn gelijk, waarmee hun producten ook gelijk zijn. Hieruit volgt: P ≡ aφ(n)P (mod n) waarbij P de eerste van die producten is. Uit het feit dat P en n relatief priem zijn, volgt dat aφ(n) ≡ 1 (mod n).
[bewerk] Toepassing
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 Eulers stelling nodig, namelijk het geval dat n=pq, waar p en q verschillende priemgetallen zijn. In het geval van cryptografie zijn p en q zeer grote priemgetallen met honderden decimalen.
