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} _{+}$$m\in {\mathbb {Z}}_{+}$ i $a\in \mathbb {Z}$$a\in {\mathbb {Z}}$ są liczbami względnie pierwszymi, to $m$$m$ dzieli liczbę $a^{\varphi (m)}-1$$a^{{\varphi (m)}}-1$, gdzie $\varphi (m)$$\varphi (m)$ oznacza wartość funkcji Eulera, czyli liczbę tych liczb całkowitych dodatnich nie większych od $m$$m$, które są z $m$$m$ względnie pierwsze.

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

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

Przykład

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

Dowód

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

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

Niech teraz $m>1$$m>1$.

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

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

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

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

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

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

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

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

Ponieważ zarówno $p_{k}$$p_{{k}}$ jak i $a$$a$ są względnie pierwsze względem $m$$m$, to również $ap_{k}$$ap_{{k}}$ ma tą własność. Załóżmy, że pewna liczba całkowita $d$$d$ dzieli zarówno $r_{k}$$r_{{k}}$ jak i $m$$m$. Ze wzoru $_{(1)}$$_{{(1)}}$ wynika, że $d$$d$ musi być równe $1$$1$, a więc $r_{k}$$r_{{k}}$ i $m$$m$ muszą być względnie pierwsze. Stąd też $r_{k}\neq 0$$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}$$(k,l)\in \{1,\,2,...,\varphi (m)\}^{{2}}$ takiej, że $k\neq l$$k\neq l$, zachodzi $f(p_{k})=f(p_{l})$$f(p_{{k}})=f(p_{{l}})$. Byłoby wtedy $ap_{k}\equiv ap_{l}{\pmod {m}}$$ap_{{k}}\equiv ap_{{l}}{\pmod m}$, a więc, ponieważ $a\neq 0$$a\neq 0$ jako liczba względnie pierwsza względem $m$$m$, byłoby też wtedy $p_{k}\equiv p_{l}{\pmod {m}}$$p_{{k}}\equiv p_{{l}}{\pmod m}$, co jest niemożliwe, skoro $p_{k},\,p_{l}$$p_{{k}},\,p_{{l}}$ są różnymi liczbami całkowitymi dodatnimi mniejszymi od $m$$m$. Zatem dla każdej pary $(k,l)\in \{1,\,2,...,\varphi (m)\}^{2}$$(k,l)\in \{1,\,2,...,\varphi (m)\}^{{2}}$ takiej, że $k\neq l$$k\neq l$, zachodzi $f(p_{k})\neq (p_{l})$$f(p_{{k}})\neq (p_{{l}})$, co kończy dowód własności 2.

Ponieważ $A=B$$A=B$, zatem $\prod \limits _{k=1}^{\varphi (m)}p_{k}=\prod \limits _{k=1}^{\varphi (m)}r_{k}$$\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}}$$\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}}$$\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}$$\prod \limits _{{k=1}}^{{\varphi (m)}}p_{{k}}$ jest względnie pierwsze z $m$$m$, zachodzi $a^{\varphi (m)}\equiv 1{\pmod {m}}\quad _{\square }$$a^{{\varphi (m)}}\equiv 1{\pmod m}\quad _{{\square }}$

Inny dowód

Niech $m\in \mathbb {Z} _{+}$$m\in {\mathbb {Z}}_{+}$ i $a\in \mathbb {Z}$$a\in {\mathbb {Z}}$ będą liczbami względnie pierwszymi, a $P=(a_{1},a_{2},\ldots ,a_{\varphi (m)})$$P=(a_{1},a_{2},\ldots ,a_{{\varphi (m)}})$ będzie ciągiem liczb naturalnych mniejszych od $m\;$$m\;$ i względnie z nim pierwszych. Wtedy ciąg $P^{\prime }=(aa_{1},aa_{2},\ldots ,aa_{\varphi (m)})$$P^{\prime }=(aa_{1},aa_{2},\ldots ,aa_{{\varphi (m)}})$ z wyrazami wziętymi ${\pmod {m}}\;$${\pmod m}\;$ jest permutacją ciągu $P\;$$P\;$. Istotnie, dla każdego $i,\ aa_{i}\;$$i,\ aa_{i}\;$ jest również względnie pierwsze z $m\;$$m\;$, zatem zachodzi $aa_{i}\equiv a_{k}{\pmod {m}}$$aa_{i}\equiv a_{k}{\pmod m}$ dla pewnego $k\;$$k\;$ i ponieważ ponadto $aa_{i}\equiv aa_{j}\Leftrightarrow a_{i}\equiv a_{j}{\pmod {m}}$$aa_{i}\equiv aa_{j}\Leftrightarrow a_{i}\equiv a_{j}{\pmod m}$ (bo z założenia $a\;$$a\;$ i $m\;$$m\;$ są względnie pierwsze), a zatem elementy ciągu $P^{\prime }\;$$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 (aa_{1})(aa_{2})\ldots (aa_{\varphi (m)}){\pmod {m}}$$a_{1}a_{2}\ldots a_{{\varphi (m)}}\equiv (aa_{1})(aa_{2})\ldots (aa_{{\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}}$$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}}$$1\equiv a^{{\varphi (m)}}{\pmod m}$

QED.