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.

De stelling van Euler zegt dat als a en n positieve gehele getallen zijn waarvoor geldt dat ze relatief priem zijn (dat wil zeggen grootste gemene deler(a,n) = 1), dan geldt

$a^{\varphi (n)} \equiv 1 \pmod{n} \,$

waar φ(n) de indicator of totiënt van n is.

Indien we veronderstellen dat n=p een priemgetal is, dan hebben we

φ(p) = p-1,

en volgt de kleine stelling van Fermat onmiddellijk.

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

Er geldt dat 7 en 10 relatief priem zijn en φ(10) = 4. De stelling van Euler levert

7⁴ ≡ 1 (mod 10)

op en we krijgen

7²²² ≡ 7^{4·55 + 2} ≡ (7⁴)⁵⁵·7² ≡ 1⁵⁵·7² ≡ 49 ≡ 9 (mod 10).

Globaal geldt dat men bij het reduceren van de macht van a modulo n (waarbij a en n relatief priem zijn) moet werken modulo φ(n) in het exponent van a: als

x ≡ y (mod φ(n)),

dan

a^x ≡ a^y (mod n).

Bewijzen

Leonhard Euler publiceerde in 1736 een bewijs. Met moderne technieken kan de stelling als volgt bewezen worden: de getallen a die relatief priem zijn met n zijn de eenheden van de ring Z/nZ en vormen een groep voor de vermenigvuldiging modulo n. 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^{\varphi (n)} \equiv 1 \pmod{n} \,$

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 stelling van Euler 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.