Stelling van Euler

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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 7222, dat is 7222 (mod 10).

Er geldt 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 modulo n (waarbij a en n relatief priem zijn) moet werken modulo φ(n) in het exponent van a: als

xy (mod φ(n)),

dan

axay (mod n).

Bewijzen[bewerken]

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:

Paφ(n)P (mod n),

waarbij P het 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[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 n=pq, waar p en q verschillende priemgetallen zijn. In het geval van cryptografie zijn p en q zeer grote priemgetallen met honderden decimalen.