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.
n
∈
N
{\ displaystyle n \ in \ mathbb {N}}
statement
Euler's theorem reads:
a
φ
(
n
)
≡
1
(
mod
n
)
{\ 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 .
gcd
(
a
,
n
)
=
1
{\ displaystyle \ operatorname {ggT} (a, n) = 1}
a
,
n
∈
N
{\ displaystyle a, n \ in \ mathbb {N}}
gcd
{\ displaystyle \ operatorname {ggT}}
a
{\ displaystyle a}
n
{\ displaystyle n}
φ
(
n
)
{\ displaystyle \ varphi (n)}
n
{\ displaystyle n}
n
{\ displaystyle n}
For prime moduli , Euler's theorem goes over to Fermat's little theorem .
p
{\ displaystyle p}
φ
(
p
)
=
p
-
1
{\ 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.
n
{\ displaystyle n}
k
{\ displaystyle k}
a
x
≡
a
x
+
k
⋅
φ
(
n
)
(
mod
n
)
{\ displaystyle a ^ {x} \ equiv a ^ {x + k \ cdot \ varphi (n)} {\ pmod {n}}}
example
What is the last digit in the decimal system of 7 222 , so which decimal digit is 7 222 congruent modulo 10?
First we notice that gcd (7,10) = 1 and that φ (10) = 4. So Euler's theorem yields
7th
4th
≡
1
(
mod
10
)
{\ displaystyle 7 ^ {4} \ equiv 1 {\ pmod {10}}}
and we receive
7th
222
=
7th
4th
⋅
55
+
2
=
(
7th
4th
)
55
⋅
7th
2
≡
1
55
⋅
7th
2
(
mod
10
)
≡
49
(
mod
10
)
≡
9
(
mod
10
)
{\ displaystyle 7 ^ {222} = 7 ^ {4 \ times 55 + 2} = (7 ^ {4}) ^ {55} \ times 7 ^ {2} \ equiv 1 ^ {55} \ times 7 ^ { 2} {\ pmod {10}} \ equiv 49 {\ pmod {10}} \ equiv 9 {\ pmod {10}}}
.
In general:
a
b
≡
a
b
mod
φ
(
n
)
(
mod
n
)
a
,
b
,
n
∈
N
∧
gcd
(
a
,
n
)
=
1
{\ 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 .
(
Z
/
n
Z
)
×
=
{
r
1
,
...
,
r
φ
(
n
)
}
{\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {\ times} = \ {r_ {1}, \ dots, r _ {\ varphi (n)} \}}
n
{\ displaystyle n}
a
{\ displaystyle a}
gcd
(
a
,
n
)
=
1
{\ displaystyle \ operatorname {ggT} (a, n) = 1}
x
↦
a
x
{\ displaystyle x \ mapsto ax}
(
Z
/
n
Z
)
×
{\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {\ times}}
a
x
≡
a
y
(
mod
n
)
{\ displaystyle ax \ equiv ay {\ pmod {n}}}
x
≡
y
(
mod
n
)
{\ displaystyle x \ equiv y {\ pmod {n}}}
Because multiplication is commutative, it follows
r
1
⋯
r
φ
(
n
)
≡
(
a
r
1
)
⋯
(
a
r
φ
(
n
)
)
≡
r
1
⋯
r
φ
(
n
)
a
φ
(
n
)
(
mod
n
)
{\ 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
r
i
{\ displaystyle r_ {i}}
i
{\ displaystyle i}
1
≡
a
φ
(
n
)
(
mod
n
)
{\ 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 .
G
{\ displaystyle G}
m
{\ displaystyle m}
m
{\ displaystyle m}
G
=
{
1
≤
a
≤
n
∣
gcd
(
a
,
n
)
=
1
}
=
(
Z
/
n
Z
)
×
{\ displaystyle G = \ {1 \ leq a \ leq n \ mid \ operatorname {ggT} (a, n) = 1 \} = (\ mathbb {Z} / n \ mathbb {Z}) ^ {\ times} }
|
G
|
=
φ
(
n
)
{\ displaystyle | G | = \ varphi (n)}
G
{\ displaystyle G}
n
{\ displaystyle n}
See also
literature
Web links
<img src="https://de.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">