Twierdzenie Eulera o liczbach względnie pierwszych

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

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

[edytuj] 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.

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

[edytuj] 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 $74 - 1,133 4 - 1,21 4 - 1$ , itd. są podzielne przez $10$ .

[edytuj] 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$ . Oczywiście $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 $a p k$ przez $m$ .

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

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

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$ ),
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ż oczywiście zawsze: $r_{k} \equiv ap_{k} \pmod m$ , a więc: $(1)$ $r k = a p k + m t 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ż $a p 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 $k,\,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 względem $m$ , zachodzi $a^{\varphi(m)} \equiv 1 \pmod m\quad_{\square}$