Twierdzenie Eulera (teoria liczb)

Twierdzenie Eulera o liczbach względnie pierwszych to twierdzenie teorii liczb, które mówi, co następuje:

Treść twierdzenia

Jeżeli $m \in \mathbb{Z} _+$ i $a \in \mathbb{Z}$ są liczbami względnie pierwszymi, to $m$ dzieli liczbę $a^{\varphi(m)}-1$, gdzie $\varphi(m)$ oznacza wartość funkcji Eulera, czyli liczbę tych liczb całkowitych dodatnich mniejszych od $m$, które są z $m$ względnie pierwsze.

Innymi słowy, zachowując powyższe oznaczenia, $a^{\varphi(m)} \equiv 1 \pmod m$.

Słabszą wersją tego twierdzenia jest małe twierdzenie Fermata.

Przykład

Mamy $\varphi(10) = 4$ — np. liczby $7, 21, 133$ są względnie pierwsze z $10$ ($7$ jest liczbą pierwszą, $21=3 \cdot 7, 133=7 \cdot 19, 10=2 \cdot 5$), dlatego też liczby $7^4-1$, $133^4-1$, $21^4-1$, itd. są podzielne przez $10$.

Dowód

Niech $m \in \mathbb{Z}_{+}$ i $a \in \mathbb{Z}$ oraz $\operatorname{NWD}(m,a)=1$.

Jeżeli $m=1$, to $\varphi(m)=1$, a więc $a^{\varphi(m)}=a$. $1|a-1$. Zatem dla $m=1$ twierdzenie jest prawdziwe.

Niech teraz $m>1$.

Przez $A$ oznaczmy zbiór $\{p_{1},\,p_{2},...,p_{\varphi(m)}\}$ liczb należących do $\mathbb{Z}_{+}$, pierwszych względem $m$ i mniejszych lub równych $m$.

Niech dla każdego $k \in \{1,\,2,...,\varphi(m)\}$, $r_{k}$ oznacza resztę z dzielenia liczby $ap_{k}$ przez $m$.

Niech $B=\{r_{1},\,r_{2},...,r_{\varphi(m)}\}$.

Udowodnimy, że $A=B$. W tym celu wystarczy pokazać, że:

1. dla każdej liczby $r_{k}$, gdzie $k \in \{1,\,2,...,\varphi(m)\}$, zachodzi $0 < r_{k} \leq m$ i $r_{k}$ jest względnie pierwsza względem $m$ (czyli $B \subseteq A$),
2. funkcja $f \colon A \to B$ opisana wzorem $f(p_{k})=r_{k}$, gdzie $k=1,\,2,...,\varphi_(m)$, jest różnowartościowa (wtedy zbiory $A$ i $B$ byłyby równoliczne, gdyż $f$ jest z definicji suriekcją),

bowiem zbiory $A$ i $B$ są skończone (a więc nie mogą być równoliczne ze swoimi podzbiorami właściwymi).

Liczby $r_{k}$ są resztami z dzielenia przez $m$, więc są większe lub równe $0$ i mniejsze od $m$.

Jest też zawsze: $r_{k} \equiv ap_{k} \pmod m$, a więc: $_{(1)}$ $r_{k}=ap_{k}+mt_{k}$ dla $k=1,\,2,...,\varphi(m)$ i $t_{k} \in \mathbb{Z}$.

Ponieważ zarówno $p_{k}$ jak i $a$ są względnie pierwsze względem $m$, to również $ap_{k}$ ma tą własność. Załóżmy, że pewna liczba całkowita $d$ dzieli zarówno $r_{k}$ jak i $m$. Ze wzoru $_{(1)}$ wynika, że $d$ musi być równe $1$, a więc $r_{k}$ i $m$ muszą być względnie pierwsze. Stąd też $r_{k} \neq 0$, co kończy dowód własności 1.

Załóżmy teraz, że dla pewnej pary $(k,l) \in \{1,\,2,...,\varphi(m)\}^{2}$ takiej, że $k \neq l$, zachodzi $f(p_{k})=f(p_{l})$. Byłoby wtedy $ap_{k} \equiv ap_{l} \pmod m$, a więc, ponieważ $a \neq 0$ jako liczba względnie pierwsza względem $m$, byłoby też wtedy $p_{k} \equiv p_{l} \pmod m$, co jest niemożliwe, skoro $p_{k},\,p_{l}$ są różnymi liczbami całkowitymi dodatnimi mniejszymi od $m$. Zatem dla każdej pary $(k,l) \in \{1,\,2,...,\varphi(m)\}^{2}$ takiej, że $k \neq l$, zachodzi $f(p_{k}) \neq (p_{l})$, co kończy dowód własności 2.

Ponieważ $A=B$, zatem $\prod\limits_{k=1}^{\varphi(m)}p_{k}=\prod\limits_{k=1}^{\varphi(m)}r_{k}$. Skoro zaś $\prod\limits_{k=1}^{\varphi(m)}r_{k} \equiv a^{\varphi(m)} \prod\limits_{k=1}^{\varphi(m)}p_{k} \pmod m$, to również $\prod\limits_{k=1}^{\varphi(m)}p_{k} \equiv a^{\varphi(m)} \prod\limits_{k=1}^{\varphi(m)}p_{k} \pmod m$. Stąd, ponieważ $\prod\limits_{k=1}^{\varphi(m)}p_{k}$ jest względnie pierwsze z $m$, zachodzi $a^{\varphi(m)} \equiv 1 \pmod m\quad_{\square}$

Inny dowód

Niech $m \in \mathbb{Z} _+$ i $a \in \mathbb{Z}$ będą liczbami względnie pierwszymi, a $P = (a_1, a_2, \ldots, a_{\varphi(m)})$ będzie ciągiem liczb naturalnych mniejszych od $m\;$ i względnie z nim pierwszych. Wtedy ciąg $P^\prime = (a a_1, a a_2, \ldots, a a_{\varphi(m)})$ z wyrazami wziętymi $\pmod m\;$ jest permutacją ciągu $P\;$. Istotnie, dla każdego $i,\ a a_i\;$ jest również względnie pierwsze z $m\;$, zatem zachodzi $a a_i \equiv a_k \pmod m$ dla pewnego $k\;$ i ponieważ ponadto $a a_i \equiv a a_j \Leftrightarrow a_i \equiv a_j \pmod m$ (bo z założenia $a\;$ i $m\;$ są względnie pierwsze), a zatem elementy ciągu $P^\prime\;$ są różne, więc istotnie jest to permutacja.

W związku z tym:

$a_1 a_2 \ldots a_{\varphi(m)} \equiv (a a_1) (a a_2) \ldots (a a_{\varphi(m)}) \pmod m$

$a_1 a_2 \ldots a_{\varphi(m)} \equiv a^{\varphi(m)} a_1 a_2 \ldots a_{\varphi(m)} \pmod m$

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

QED.