Twierdzenie Eulera (teoria liczb)

Twierdzenie Eulera – twierdzenie w teorii liczb będące uogólnieniem małego twierdzenia Fermata na liczby złożone^[1]. Podobnie jak małe twierdzenie Fermata, jest ono wnioskiem z zastosowania twierdzenia Lagrange’a dla grupy multiplikatywnej reszt modulo ${\displaystyle n}$^[2]. Po raz pierwszy zostało udowodnione w pracy szwajcarskiego matematyka, Leonharda Eulera, opublikowanej w 1763 roku^[3].

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

Ten artykuł dotyczy twierdzenia teorii liczb. Zobacz też: inne twierdzenia o tej samej nazwie.

Twierdzenie[1][4]

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

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

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

Przykłady

Łatwo sprawdzić, że ${\displaystyle \varphi (10)=4,}$ czyli są dokładnie cztery dodatnie liczby całkowite nie większe od ${\displaystyle 10,}$ które są z ${\displaystyle 10}$ względnie pierwsze. Liczby

${\displaystyle 7,\quad 21=3\cdot 7,\quad 133=7\cdot 19}$

są oczywiście względnie pierwsze z ${\displaystyle 10,}$ ponieważ nie są podzielne przez ${\displaystyle 2}$ ani przez ${\displaystyle 5.}$ Twierdzenie Eulera orzeka, że każda z liczb

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

jest podzielna przez ${\displaystyle 10.}$

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

Dowód[5]

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

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

Niech teraz ${\displaystyle m>1.}$

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

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

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

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

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

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

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

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

Ponieważ zarówno ${\displaystyle p_{k},}$ jak i ${\displaystyle a}$ są względnie pierwsze względem ${\displaystyle m,}$ to również ${\displaystyle ap_{k}}$ ma tę własność. Załóżmy, że pewna liczba całkowita ${\displaystyle d}$ dzieli zarówno ${\displaystyle r_{k},}$ jak i ${\displaystyle m.}$ Ze wzoru ${\displaystyle _{(1)}}$ wynika, że ${\displaystyle d}$ musi być równe ${\displaystyle 1,}$ a więc ${\displaystyle r_{k}}$ i ${\displaystyle m}$ muszą być względnie pierwsze. Stąd też ${\displaystyle r_{k}\neq 0,}$ co kończy dowód własności 1.

Załóżmy teraz, że dla pewnej pary ${\displaystyle (k,l)\in \{1,\,2,\dots ,\varphi (m)\}^{2}}$ takiej, że ${\displaystyle k\neq l,}$ zachodzi ${\displaystyle f(p_{k})=f(p_{l}).}$ Byłoby wtedy ${\displaystyle ap_{k}\equiv ap_{l}{\pmod {m}},}$ a więc, ponieważ ${\displaystyle a\neq 0}$ jako liczba względnie pierwsza względem ${\displaystyle m,}$ byłoby też wtedy ${\displaystyle p_{k}\equiv p_{l}{\pmod {m}},}$ co jest niemożliwe, skoro ${\displaystyle p_{k},\,p_{l}}$ są różnymi liczbami całkowitymi dodatnimi mniejszymi od ${\displaystyle m.}$ Zatem dla każdej pary ${\displaystyle (k,l)\in \{1,\,2,\dots ,\varphi (m)\}^{2}}$ takiej, że ${\displaystyle k\neq l,}$ zachodzi ${\displaystyle f(p_{k})\neq (p_{l}),}$ co kończy dowód własności 2.

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

Inny dowód[6]

Niech ${\displaystyle m\in \mathbb {Z} _{+}}$ i ${\displaystyle a\in \mathbb {Z} }$ będą liczbami względnie pierwszymi, a ${\displaystyle P=(a_{1},a_{2},\dots ,a_{\varphi (m)})}$ będzie ciągiem liczb naturalnych mniejszych od ${\displaystyle m}$ i względnie z nim pierwszych. Wtedy ciąg ${\displaystyle P'=(aa_{1},aa_{2},\dots ,aa_{\varphi (m)})}$ z wyrazami wziętymi ${\displaystyle {\pmod {m}}}$ jest permutacją ciągu ${\displaystyle P.}$ Istotnie, dla każdego ${\displaystyle i,\ aa_{i}}$ jest również względnie pierwsze z ${\displaystyle m,}$ zatem zachodzi ${\displaystyle aa_{i}\equiv a_{k}{\pmod {m}}}$ dla pewnego ${\displaystyle k}$ i ponieważ ponadto ${\displaystyle aa_{i}\equiv aa_{j}\Leftrightarrow a_{i}\equiv a_{j}{\pmod {m}}}$ (bo z założenia ${\displaystyle a}$ i ${\displaystyle m}$ są względnie pierwsze), a zatem elementy ciągu ${\displaystyle P'}$ są różne, więc istotnie jest to permutacja.

W związku z tym:

${\displaystyle a_{1}a_{2}\ldots a_{\varphi (m)}\equiv (aa_{1})(aa_{2})\ldots (aa_{\varphi (m)}){\pmod {m}},}$

${\displaystyle a_{1}a_{2}\ldots a_{\varphi (m)}\equiv a^{\varphi (m)}a_{1}a_{2}\ldots a_{\varphi (m)}{\pmod {m}},}$

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

q.e.d.

Zobacz też

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