Enunţ [ ]
Teoremă .
Dacă a , n sunt două numere întregi prime între ele, atunci:
a
φ
(
n
)
≡
1
(
m
o
d
n
)
.
{\displaystyle a^{\varphi(n)} \equiv 1 \; (mod \; n). \!}
unde
φ
{\displaystyle \varphi \!}
este indicatorul lui Euler (funcţia
φ
{\displaystyle \varphi \!}
a lui Euler ).
(Mai este numită şi teorema Fermat -Euler .)
Teorema este o generalizare pentru mica teoremă a lui Fermat .
Demonstraţie [ ]
Fie
p
1
,
p
2
,
⋯
,
p
φ
(
n
)
{\displaystyle p_1, p_2, \cdots , p_{\varphi(n)} \!}
numerele prime cu n şi mai mici decât acesta şi
r
1
,
r
2
,
⋯
,
r
φ
(
n
)
{\displaystyle r_1, r_2, \cdots , r_{\varphi(n)} \!}
resturile împărţirii lui
a
p
1
,
a
p
2
,
⋯
,
a
p
φ
(
n
)
{\displaystyle ap_1, ap_2, \cdots , ap_{\varphi (n)} \!}
la n .
Să arătăm că numerele
r
1
,
r
2
,
⋯
,
r
φ
(
n
)
{\displaystyle r_1, r_2, \cdots , r_{\varphi(n)} \!}
sunt chiar numerele
p
1
,
p
2
,
⋯
,
p
φ
(
n
)
{\displaystyle p_1, p_2, \cdots , p_{\varphi(n)} \!}
eventual luate în altă ordine, adică:
{
p
1
,
p
2
,
⋯
,
p
φ
(
n
)
}
=
{
r
1
,
r
2
,
⋯
,
r
φ
(
n
)
}
.
{\displaystyle \{ p_1, p_2, \cdots , p_{\varphi(n)} \} = \{ r_1, r_2, \cdots , r_{\varphi(n)} \}. \!}
Conform teoremei 1 de la Teoria numerelor , resturile împărţirii la n a numerelor
a
,
2
a
,
⋯
n
a
{\displaystyle a, 2a, \cdots na \!}
sunt distincte două câte două.
Deci
r
1
,
r
2
,
⋯
,
r
φ
(
n
)
{\displaystyle r_1, r_2, \cdots , r_{\varphi(n)} \!}
sunt distincte între ele deoarece şi numerele
a
p
1
,
a
p
2
,
⋯
,
a
p
φ
(
n
)
{\displaystyle ap_1, ap_2, \cdots , ap_{\varphi (n)} \!}
se află printre numerele
a
,
2
a
,
⋯
,
n
a
{\displaystyle a, 2a, \cdots , na \!}
(căci
p
1
,
p
2
,
⋯
,
p
φ
(
n
)
{\displaystyle p_1, p_2, \cdots , p_{\varphi(n)} \!}
sunt mai mici decât n ).
Resurse [ ]