Twierdzenie Eulera o liczbach względnie pierwszych to twierdzenie teorii liczb, które mówi, co następuje:
Jeżeli
i
są liczbami względnie pierwszymi, to
dzieli liczbę
gdzie
oznacza wartość funkcji Eulera, czyli liczbę tych liczb całkowitych dodatnich nie większych od
które są z
względnie pierwsze.
Innymi słowy, zachowując powyższe oznaczenia,
Słabszą wersją tego twierdzenia jest małe twierdzenie Fermata.
Mamy
– np. liczby
są względnie pierwsze z
(
jest liczbą pierwszą,
), dlatego też liczby
itd. są podzielne przez
Niech
i
oraz
Jeżeli
to
a więc
Zatem dla
twierdzenie jest prawdziwe.
Niech teraz
Przez
oznaczmy zbiór
liczb należących do
pierwszych względem
i mniejszych lub równych
Niech dla każdego
oznacza resztę z dzielenia liczby
przez
Niech
Udowodnimy, że
W tym celu wystarczy pokazać, że:
- dla każdej liczby
gdzie
zachodzi
i
jest względnie pierwsza względem
(czyli
),
- funkcja
opisana wzorem
gdzie
jest różnowartościowa (wtedy zbiory
i
byłyby równoliczne, gdyż
jest z definicji suriekcją),
bowiem zbiory
i
są skończone (a więc nie mogą być równoliczne ze swoimi podzbiorami właściwymi).
Liczby
są resztami z dzielenia przez
więc są większe lub równe
i mniejsze od
Jest też zawsze:
a więc:
dla
i
Ponieważ zarówno
jak i
są względnie pierwsze względem
to również
ma tę własność. Załóżmy, że pewna liczba całkowita
dzieli zarówno
jak i
Ze wzoru
wynika, że
musi być równe
a więc
i
muszą być względnie pierwsze. Stąd też
co kończy dowód własności 1.
Załóżmy teraz, że dla pewnej pary
takiej, że
zachodzi
Byłoby wtedy
a więc, ponieważ
jako liczba względnie pierwsza względem
byłoby też wtedy
co jest niemożliwe, skoro
są różnymi liczbami całkowitymi dodatnimi mniejszymi od
Zatem dla każdej pary
takiej, że
zachodzi
co kończy dowód własności 2.
Ponieważ
zatem
Skoro zaś
to również
Stąd, ponieważ
jest względnie pierwsze z
zachodzi
Niech
i
będą liczbami względnie pierwszymi, a
będzie ciągiem liczb naturalnych mniejszych od
i względnie z nim pierwszych. Wtedy ciąg
z wyrazami wziętymi
jest permutacją ciągu
Istotnie, dla każdego
jest również względnie pierwsze z
zatem zachodzi
dla pewnego
i ponieważ ponadto
(bo z założenia
i
są względnie pierwsze), a zatem elementy ciągu
są różne, więc istotnie jest to permutacja.
W związku z tym:



q.e.d.