Twierdzenie Eulera (teoria liczb)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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

Treść twierdzenia[edytuj | edytuj kod]

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

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[1][edytuj | edytuj kod]

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 Bskoń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 [2][edytuj | edytuj kod]

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.

Przypisy

  1. Dowód ten jest przeredagowaną wersją dowodu zawartego w książce Wacława Sierpińskiego Wstęp do teorii liczb.
  2. Naoki Sato: Number Theory (ang.). [dostęp 03.06.2009]. s. 14-15.