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

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

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

waar $\varphi (n)$ de indicator of totiënt van $n$ is.

Voor $p$ een priemgetal, volgt dan

$\varphi (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 $\varphi (10)=4.$ De stelling van Euler levert

$7^{4}\equiv 1{\pmod {10}}$

op en we krijgen

$7^{222}\equiv 7^{4\times 55+2}=\left(7^{4}\right)^{55}\times 7^{2}\equiv 1^{55}\times 49=49\equiv 9{\pmod {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 $\varphi (n)$ in de exponent van $a$. Dus

$a^{x}\equiv a^{y}{\pmod {n}}$,

als

$x\equiv y{\pmod {\varphi (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 $\mathbb {Z} /n\mathbb {Z}$ en vormen een groep voor de vermenigvuldiging modulo $n$. Deze groep heeft $\varphi (n)$ elementen en de stelling van Euler volgt dan uit de stelling van Lagrange.

Alternatief bewijs

Er is ook een direct bewijs. Als $R=\{x_{1},x_{2},\ldots ,x_{\varphi (n)}\},{\pmod {n}}$ een gereduceerd reststelsel is en $a$ is relatief priem met $n$, betekent vermenigvuldigen van de elementen van $R$ met $a$ een permutatie, dus $aR=\{ax_{1},ax_{2},\ldots ,ax_{\varphi (n)}\}=R{\pmod {n}}$. Dan volgt uit $ax_{i}=ax_{j}\!\!{\pmod {n}}$, dat $i=j$. Omdat

$\prod _{i=1}^{\varphi (n)}x_{i}\equiv \prod _{i=1}^{\varphi (n)}ax_{i}\equiv a^{\varphi (n)}\prod _{i=1}^{\varphi (n)}x_{i}{\pmod {n}},$

volgt ook:

$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$, waarin $p$ en $q$ verschillende priemgetallen zijn. In het geval van cryptografie zijn $p$ en $q$ zeer grote priemgetallen bestaande uit honderden cijfers.