Twierdzenie Eulera (teoria liczb)

Leonhard Euler, szwajcarski matematyk, którego nazwiskiem zostało nazwane twierdzenie.

Szablon:Inne znaczeniaTwierdzenie Eulera – twierdzenie w teorii liczb będące uogólnieniem małego twierdzenia Fermata na liczby złożone. Podobnie jak małe twierdzenie Fermata, jest ono wnioskiem z zastosowania twierdzenia Lagrange’a dla grupy multiplikatywnej reszt modulo

$n$

. Po raz pierwszy zostało udowodnione w pracy szwajcarskiego matematyka, Leonharda Eulera, opublikowanej w 1763 roku.

Twierdzenie

Niech $a$ i $n$ będą względnie pierwszymi dodatnimi liczbami całkowitymi. Wówczas Szablon:Wzór gdzie $\phi (n)$ oznacza liczbę dodatnich liczb całkowitych nie większych od $n,$ które są z $n$ względnie pierwsze. Funkcję $\phi$ nazywa się funkcją Eulera lub tocjentem.

Przykłady

Łatwo sprawdzić, że $\phi (10)=4,$ czyli są dokładnie cztery dodatnie liczby całkowite nie większe od $10,$ które są z $10$ względnie pierwsze. Liczby Szablon:Wzór są oczywiście względnie pierwsze z $10,$ ponieważ nie są podzielne przez $2$ ani przez $5.$ Twierdzenie Eulera orzeka, że każda z liczb Szablon:Wzór jest podzielna przez $10.$

Jeśli $n$ jest liczbą pierwszą, to $\phi (n)=n-1.$ W tym przypadku twierdzenie Eulera jest równoważne małemu twierdzeniu Fermata.

Dowód

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

Jeżeli $m=1,$ to $\phi (m)=1,$ a więc $a^{\phi (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,\dots ,p_{\phi (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,\dots ,\phi (m)\},$ $r_k$ oznacza resztę z dzielenia liczby $a{p}_k$ przez $m.$

Niech $B=\{r_1,r_2,\dots ,r_{\phi (m)}\}.$

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

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

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 a{p}_k(\mathrm{mod}m),$ a więc: ${}_{(1)}$ $r_k=a{p}_k+m{t}_k$ dla $k=1,2,\dots ,\phi (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\ne 0,$ co kończy dowód własności 1.

Załóżmy teraz, że dla pewnej pary $(k,l)\in \{1,2,\dots ,\phi (m){\}}^2$ takiej, że $k\ne l,$ zachodzi $f(p_k)=f(p_l).$ Byłoby wtedy $a{p}_k\equiv a{p}_l(\mathrm{mod}m),$ a więc, ponieważ $a\ne 0$ jako liczba względnie pierwsza względem $m,$ byłoby też wtedy $p_k\equiv p_l(\mathrm{mod}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,\dots ,\phi (m){\}}^2$ takiej, że $k\ne l,$ zachodzi $f(p_k)\ne (p_l),$ co kończy dowód własności 2.

Ponieważ $A=B,$ zatem $\prod _{k=1}^{\phi (m)}{p}_k=\prod _{k=1}^{\phi (m)}{r}_k.$ Skoro zaś $\prod _{k=1}^{\phi (m)}{r}_k\equiv a^{\phi (m)}\prod _{k=1}^{\phi (m)}{p}_k(\mathrm{mod}m),$ to również $\prod _{k=1}^{\phi (m)}{p}_k\equiv a^{\phi (m)}\prod _{k=1}^{\phi (m)}{p}_k(\mathrm{mod}m).$ Stąd, ponieważ $\prod _{k=1}^{\phi (m)}{p}_k$ jest względnie pierwsze z $m,$ zachodzi $a^{\phi (m)}\equiv 1(\mathrm{mod}m){}_{◻}$

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,\dots ,a_{\phi (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,\dots ,a{a}_{\phi (m)})$ z wyrazami wziętymi $(\mathrm{mod}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(\mathrm{mod}m)$ dla pewnego $k$ i ponieważ ponadto $a{a}_i\equiv a{a}_j\iff a_i\equiv a_j(\mathrm{mod}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\dots a_{\phi (m)}\equiv (a{a}_1)(a{a}_2)\dots (a{a}_{\phi (m)})(\mathrm{mod}m),$

$a_1{a}_2\dots a_{\phi (m)}\equiv a^{\phi (m)}{a}_1{a}_2\dots a_{\phi (m)}(\mathrm{mod}m),$

$1\equiv a^{\phi (m)}(\mathrm{mod}m).$

q.e.d.

Zobacz też

• małe twierdzenie Fermata
• funkcja φ
• funkcja Carmichaela,
• twierdzenie Wilsona

Linki zewnętrzne

• Szablon:MathWorld [dostęp 2024-02-02].