Stelling van Euler

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.

Stelling

De stelling van Euler zegt dat als ${\displaystyle a}$ en ${\displaystyle n}$ positieve gehele getallen zijn waarvoor geldt dat ze onderling ondeelbaar zijn, wat wil zeggen dat de grootste gemene deler van ${\displaystyle a}$ en ${\displaystyle n}$ gelijk is aan 1, dat dan geldt

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

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

Voor ${\displaystyle p}$ een priemgetal, volgt dan

${\displaystyle \varphi (p)=p-1}$,

en volgt de kleine stelling van Fermat onmiddellijk.

Voorbeeld

De stelling kan worden gebruikt om de berekening van hoge machten modulo ${\displaystyle n}$ te vereenvoudigen. Ter illustratie beschrijven we de berekening van het laatste decimale cijfer van 7^222, dat is ${\displaystyle 7^{222}\ {\text{mod}}\ 10}$.

Er geldt dat 7 en 10 relatief priem zijn en ${\displaystyle \varphi (10)=4}$.

${\displaystyle 7^{4}\equiv 1\mod {10}}$

volgens de stelling van Euler en

${\displaystyle 7^{222}\equiv 7^{4\times 55+2}=\left(7^{4}\right)^{55}\times 7^{2}\equiv 1^{55}\times 49=49\equiv 9\mod {10}}$.

Er geldt dat

${\displaystyle a^{x}\equiv a^{y}\mod {n}}$,

als

${\displaystyle x\equiv y\mod {\varphi (n)}}$.

Bewijzen

Leonhard Euler publiceerde in 1736 een bewijs.

Het bewijs kan worden gegeven door te stellen dat de getallen ${\displaystyle a}$ die relatief priem zijn met ${\displaystyle n}$ de eenheden van de ring ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ zijn en een groep vormen voor de vermenigvuldiging modulo ${\displaystyle n}$. Deze groep heeft ${\displaystyle \varphi (n)}$ elementen en de stelling van Euler volgt dan uit de stelling van Lagrange.

Bewijs 

Als ${\displaystyle R=\{x_{1},x_{2},\ldots ,x_{\varphi (n)}\}\ {\text{mod}}\ n}$ een gereduceerd reststelsel is en ${\displaystyle a}$ onderling ondeelbaar met ${\displaystyle n}$ is, betekent vermenigvuldigen van de elementen van ${\displaystyle R}$ met ${\displaystyle a}$ een permutatie, dus ${\displaystyle aR=\{ax_{1},ax_{2},\ldots ,ax_{\varphi (n)}\}=R\ {\text{mod}}\ n}$. Dan volgt uit ${\displaystyle ax_{i}=ax_{j}\ {\text{mod}}\ n}$, dat ${\displaystyle i=j}$. Omdat

${\displaystyle \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}\mod {n},}$

volgt ook:

${\displaystyle a^{\varphi (n)}\equiv 1\mod {n}}$.

RSA-algoritme

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 ${\displaystyle n=pq}$, waarin ${\displaystyle p}$ en ${\displaystyle q}$ verschillende priemgetallen zijn. In het geval van cryptografie zijn ${\displaystyle p}$ en ${\displaystyle q}$ zeer grote priemgetallen die uit honderden cijfers bestaan.