Twierdzenie Eulera (teoria liczb)

Twierdzenie 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.

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

Twierdzenie

Niech $a$ i $n$ będą względnie pierwszymi dodatnimi liczbami całkowitymi. Wówczas

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

gdzie $\varphi (n)$ oznacza liczbę dodatnich liczb całkowitych nie większych od $n,$ które są z $n$ względnie pierwsze. Funkcję $\varphi$ nazywa się funkcją Eulera lub tocjentem.

Przykłady

Łatwo sprawdzić, że $\varphi (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

$7,\quad 21=3\cdot 7,\quad 133=7\cdot 19$

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

$7^{4}-1,\quad 21^{4}-1,\quad 133^{4}-1$

jest podzielna przez $10.$

Jeśli $n$ jest liczbą pierwszą, to $\varphi (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 $\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},\dots ,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,\dots ,\varphi (m)\},$ $r_{k}$ oznacza resztę z dzielenia liczby $ap_{k}$ przez $m.$

Niech $B=\{r_{1},\,r_{2},\dots ,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,\dots ,\varphi (m)\},$ zachodzi $0<r_{k}\leqslant 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,\dots ,\varphi _{(}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 ap_{k}{\pmod {m}},$ a więc: $_{(1)}$ $r_{k}=ap_{k}+mt_{k}$ dla $k=1,\,2,\dots ,\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,\dots ,\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,\dots ,\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},\dots ,a_{\varphi (m)})$ będzie ciągiem liczb naturalnych mniejszych od $m$ i względnie z nim pierwszych. Wtedy ciąg $P'=(aa_{1},aa_{2},\dots ,aa_{\varphi (m)})$ z wyrazami wziętymi ${\pmod {m}}$ jest permutacją ciągu $P.$ Istotnie, dla każdego $i,\ aa_{i}$ jest również względnie pierwsze z $m,$ zatem zachodzi $aa_{i}\equiv a_{k}{\pmod {m}}$ dla pewnego $k$ i ponieważ ponadto $aa_{i}\equiv aa_{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'$ 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 a^{\varphi (m)}a_{1}a_{2}\ldots a_{\varphi (m)}{\pmod {m}},$

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

q.e.d.

Zobacz też

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

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Euler’s Totient Theorem, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2024-02-02].