Euler's theorem

The title of this article is ambiguous. Further meanings are listed under Euler's Theorem (disambiguation) .

The Euler's theorem , also known as Euler-Fermat named after Leonhard Euler and Pierre de Fermat , is a generalization of the Fermat's little theorem to arbitrary (not necessarily prime) moduli represent. ${\displaystyle n\in \mathbb {N} }$

statement

Euler's theorem reads:

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

It applies under the condition with , wherein the greatest common divisor of two integers and is and the Euler's φ function referred to, namely the number of prime modulo radicals . ${\displaystyle \operatorname {ggT} (a,n)=1}$ ${\displaystyle a,n\in \mathbb {N} }$ ${\displaystyle \operatorname {ggT} }$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle \varphi (n)}$ ${\displaystyle n}$ ${\displaystyle n}$

For prime moduli , Euler's theorem goes over to Fermat's little theorem . ${\displaystyle p}$ ${\displaystyle \varphi (p)=p-1}$

Applications

Euler's theorem serves to reduce large exponents modulo . From it it follows for whole numbers that . In this capacity, it finds practical application in computer-aided cryptography , for example in the RSA encryption process. ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle a^{x}\equiv a^{x+k\cdot \varphi (n)}{\pmod {n}}}$

example

What is the last digit in the decimal system of 7 ²²² , so which decimal digit is 7 ²²² congruent modulo 10?

First we notice that gcd (7,10) = 1 and that φ (10) = 4. So Euler's theorem yields

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

and we receive

${\displaystyle 7^{222}=7^{4\cdot 55+2}=(7^{4})^{55}\cdot 7^{2}\equiv 1^{55}\cdot 7^{2}{\pmod {10}}\equiv 49{\pmod {10}}\equiv 9{\pmod {10}}}$.

In general:

${\displaystyle a^{b}\equiv a^{b{\bmod {\varphi }}(n)}{\pmod {n}}\qquad a,b,n\in \mathbb {N} \wedge \operatorname {ggT} (a,n)=1}$

Proof of Euler's theorem

Let be the set of multiplicative modulo invertible elements. For each with there is then a permutation of , because from follows . ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }=\{r_{1},\dots ,r_{\varphi (n)}\}}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle \operatorname {ggT} (a,n)=1}$ ${\displaystyle x\mapsto ax}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ ${\displaystyle ax\equiv ay{\pmod {n}}}$ ${\displaystyle x\equiv y{\pmod {n}}}$

Because multiplication is commutative, it follows

${\displaystyle r_{1}\cdots r_{\varphi (n)}\equiv (ar_{1})\cdots (ar_{\varphi (n)})\equiv r_{1}\cdots r_{\varphi (n)}a^{\varphi (n)}{\pmod {n}}}$,

and since they are invertible for all , the following applies ${\displaystyle r_{i}}$ ${\displaystyle i}$

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

Alternative evidence

Euler's theorem is a direct consequence of Lagrange's theorem from group theory : In every group with finite order , the -th power of each element is the one element. So here is where the operation of multiplication is modulo . ${\displaystyle G}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle G=\{1\leq a\leq n\mid \operatorname {ggT} (a,n)=1\}=(\mathbb {Z} /n\mathbb {Z} )^{\times }}$ ${\displaystyle |G|=\varphi (n)}$ ${\displaystyle G}$ ${\displaystyle n}$

See also

• Carmichael function
• congruence
• Divisibility
• Number theory
• Cryptography

literature

• Harald Scheid : Number Theory , Spectrum Academic Publishing House, 2003, ISBN 3-8274-1365-6

Web links

• Christian Spannagel : Theorems of Euler and Fermat . Lecture series, 2012.