Twierdzenie Eulera (teoria liczb): Różnice pomiędzy wersjami
[wersja przejrzana] | [wersja przejrzana] |
Epsilon598 (dyskusja | edycje) lead |
Epsilon598 (dyskusja | edycje) poprawiona treść twierdzenia i przykład, źródła/przypisy, zobacz też Znaczniki: VisualEditor Link do ujednoznacznienia |
||
Linia 1: | Linia 1: | ||
⚫ | [[Plik:Leonhard Euler.jpg|mały|[[Leonhard Euler]], szwajcarski matematyk, którego nazwiskiem zostało nazwane twierdzenie.]]{{Inne znaczenia|twierdzenia teorii liczb|[[Twierdzenie Eulera|inne twierdzenia]] o tej samej nazwie}}'''Twierdzenie Eulera''' – twierdzenie w [[teoria liczb|teorii liczb]] będące uogólnieniem [[Małe twierdzenie Fermata|małego twierdzenia Fermata]] na liczby złożone<ref name=":0">{{Cytuj |autor = Ronald Graham; Donald Knuth; Oren Patashnik |tytuł = Matematyka konkretna |data = 2012 |isbn = 9788301147648 |wydawca = Wydawnictwo Naukowe PWN |s = 159 |język = pl}}</ref>. Podobnie jak małe twierdzenie Fermata, jest ono wnioskiem z zastosowania [[Twierdzenie Lagrange’a (teoria grup)|twierdzenia Lagrange’a]] dla [[Arytmetyka modularna#Grupa multiplikatywna|grupy multiplikatywnej reszt]] modulo <math>n</math><ref>{{Cytuj |autor = Władysław Narkiewicz |tytuł = Teoria liczb |data = 2003 |isbn = 8301140151 |wydawca = Wydawnictwo Naukowe PWN |s = 51 |język = pl}}</ref>. Po raz pierwszy zostało udowodnione w pracy szwajcarskiego matematyka, [[Leonhard Euler|Leonharda Eulera]], opublikowanej w 1963 roku<ref>{{Cytuj |autor = Leonhard Euler |tytuł = Theoremata arithmetica nova methodo demonstrata |czasopismo = Novi Commentarii academiae scientiarum Petropolitanae |data = 1763 |data dostępu = 2024-03-28 |wolumin = 8 |s = 74–104 |url = https://scholarlycommons.pacific.edu/euler-works/271 |język = la}}</ref>. |
||
[[Plik:Leonhard Euler.jpg|mały|[[Leonhard Euler]], szwajcarski matematyk, którego nazwiskiem zostało nazwane twierdzenie.]] |
|||
⚫ | '''Twierdzenie Eulera''' – twierdzenie w [[teoria liczb|teorii liczb]] będące uogólnieniem [[Małe twierdzenie Fermata|małego twierdzenia Fermata]] na liczby złożone<ref>{{Cytuj |autor = Ronald Graham; Donald Knuth; Oren Patashnik |tytuł = Matematyka konkretna |data = 2012 |isbn = 9788301147648 |wydawca = Wydawnictwo Naukowe PWN |s = 159 |język = pl}}</ref>. Podobnie jak małe twierdzenie Fermata, jest ono wnioskiem z zastosowania [[Twierdzenie Lagrange’a (teoria grup)|twierdzenia Lagrange’a]] dla [[Arytmetyka modularna#Grupa multiplikatywna|grupy multiplikatywnej reszt]] modulo <math>n</math><ref>{{Cytuj |autor = Władysław Narkiewicz |tytuł = Teoria liczb |data = 2003 |isbn = 8301140151 |wydawca = Wydawnictwo Naukowe PWN |s = 51 |język = pl}}</ref>. |
||
== Twierdzenie<ref name=":0" /><ref>{{Cytuj |autor = Adam Neugebauer |tytuł = Algebra i teoria liczb |data = 2020 |isbn = 9788372677105 |wydawca = Wydawnictwo Szkolne OMEGA |s = 165 |seria = Matematyka olimpijska |język = pl}}</ref> == |
|||
== Twierdzenie == |
|||
Niech <math>a</math> i <math>n</math> będą [[liczby względnie pierwsze|względnie pierwszymi]] dodatnimi [[Liczby całkowite|liczbami całkowitymi]]. Wówczas |
|||
{{Wzór|<math> a^{\varphi(n)} \equiv 1 \pmod{n},</math>}} |
|||
gdzie <math>\varphi(n)</math> oznacza liczbę dodatnich liczb całkowitych nie większych od <math>n,</math> które są z <math>n</math> względnie pierwsze. Funkcję <math>\varphi</math> nazywa się [[Funkcja φ|funkcją Eulera]] lub tocjentem. |
|||
⚫ | |||
== |
== Przykłady == |
||
Łatwo sprawdzić, że <math>\varphi(10) = 4,</math> czyli są dokładnie cztery dodatnie liczby całkowite nie większe od <math>10,</math> które są z <math>10</math> względnie pierwsze. Liczby |
|||
Mamy <math>\varphi(10) = 4</math> – np. liczby <math>7, 21, 133</math> są względnie pierwsze z <math>10</math> (<math>7</math> jest [[Liczba pierwsza|liczbą pierwszą]], <math>21=3 \cdot 7, 133=7 \cdot 19, 10=2 \cdot 5</math>), dlatego też liczby <math>7^4-1,</math> <math>133^4-1,</math> <math>21^4-1,</math> itd. są podzielne przez <math>10.</math> |
|||
{{Wzór|<math> 7, \quad 21 = 3\cdot 7, \quad133 = 7\cdot 19</math>}} |
|||
są oczywiście względnie pierwsze z <math>10,</math> ponieważ nie są podzielne przez <math>2</math> ani przez <math>5.</math> Twierdzenie Eulera orzeka, że każda z liczb |
|||
{{Wzór|<math> 7^4 - 1,\quad 21^4 - 1, \quad 133^4 - 1</math>}} |
|||
jest podzielna przez <math>10.</math> |
|||
Jeśli <math>n</math> jest liczbą pierwszą, to <math>\varphi(n) = n - 1.</math> W tym przypadku twierdzenie Eulera jest równoważne [[Małe twierdzenie Fermata|małemu twierdzeniu Fermata]]. |
|||
== Dowód<ref>Dowód ten jest przeredagowaną wersją dowodu zawartego w książce [[Wacław Sierpiński|Wacława Sierpińskiego]] ''Wstęp do teorii liczb''.</ref> == |
== Dowód<ref>Dowód ten jest przeredagowaną wersją dowodu zawartego w książce [[Wacław Sierpiński|Wacława Sierpińskiego]] ''Wstęp do teorii liczb''.</ref> == |
||
Linia 50: | Linia 59: | ||
[[q.e.d.]] |
[[q.e.d.]] |
||
== Zobacz też == |
|||
⚫ | |||
* [[funkcja φ]] |
|||
* [[funkcja Carmichaela]], |
|||
* [[twierdzenie Wilsona]] |
|||
== Przypisy == |
== Przypisy == |
Wersja z 20:20, 28 mar 2024
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 [2]. Po raz pierwszy zostało udowodnione w pracy szwajcarskiego matematyka, Leonharda Eulera, opublikowanej w 1963 roku[3].
Niech i będą względnie pierwszymi dodatnimi liczbami całkowitymi. Wówczas
gdzie oznacza liczbę dodatnich liczb całkowitych nie większych od które są z względnie pierwsze. Funkcję nazywa się funkcją Eulera lub tocjentem.
Przykłady
Łatwo sprawdzić, że czyli są dokładnie cztery dodatnie liczby całkowite nie większe od które są z względnie pierwsze. Liczby
są oczywiście względnie pierwsze z ponieważ nie są podzielne przez ani przez Twierdzenie Eulera orzeka, że każda z liczb
jest podzielna przez
Jeśli jest liczbą pierwszą, to W tym przypadku twierdzenie Eulera jest równoważne małemu twierdzeniu Fermata.
Dowód[5]
Niech i oraz
Jeżeli to a więc Zatem dla twierdzenie jest prawdziwe.
Niech teraz
Przez oznaczmy zbiór liczb należących do pierwszych względem i mniejszych lub równych
Niech dla każdego oznacza resztę z dzielenia liczby przez
Niech
Udowodnimy, że W tym celu wystarczy pokazać, że:
- dla każdej liczby gdzie zachodzi i jest względnie pierwsza względem (czyli ),
- funkcja opisana wzorem gdzie jest różnowartościowa (wtedy zbiory i byłyby równoliczne, gdyż jest z definicji surjekcją),
bowiem zbiory i są skończone (a więc nie mogą być równoliczne ze swoimi podzbiorami właściwymi).
Liczby są resztami z dzielenia przez więc są większe lub równe i mniejsze od
Jest też zawsze: a więc: dla i
Ponieważ zarówno jak i są względnie pierwsze względem to również ma tę własność. Załóżmy, że pewna liczba całkowita dzieli zarówno jak i Ze wzoru wynika, że musi być równe a więc i muszą być względnie pierwsze. Stąd też co kończy dowód własności 1.
Załóżmy teraz, że dla pewnej pary takiej, że zachodzi Byłoby wtedy a więc, ponieważ jako liczba względnie pierwsza względem byłoby też wtedy co jest niemożliwe, skoro są różnymi liczbami całkowitymi dodatnimi mniejszymi od Zatem dla każdej pary takiej, że zachodzi co kończy dowód własności 2.
Ponieważ zatem Skoro zaś to również Stąd, ponieważ jest względnie pierwsze z zachodzi
Inny dowód[6]
Niech i będą liczbami względnie pierwszymi, a będzie ciągiem liczb naturalnych mniejszych od i względnie z nim pierwszych. Wtedy ciąg z wyrazami wziętymi jest permutacją ciągu Istotnie, dla każdego jest również względnie pierwsze z zatem zachodzi dla pewnego i ponieważ ponadto (bo z założenia i są względnie pierwsze), a zatem elementy ciągu są różne, więc istotnie jest to permutacja.
W związku z tym:
Zobacz też
Przypisy
- ↑ a b Ronald Graham , Donald Knuth , Oren Patashnik , Matematyka konkretna, Wydawnictwo Naukowe PWN, 2012, s. 159, ISBN 978-83-01-14764-8 (pol.).
- ↑ Władysław Narkiewicz , Teoria liczb, Wydawnictwo Naukowe PWN, 2003, s. 51, ISBN 83-01-14015-1 (pol.).
- ↑ Leonhard Euler , Theoremata arithmetica nova methodo demonstrata, „Novi Commentarii academiae scientiarum Petropolitanae”, 8, 1763, s. 74–104 [dostęp 2024-03-28] (łac.).
- ↑ Adam Neugebauer , Algebra i teoria liczb, Wydawnictwo Szkolne OMEGA, 2020 (Matematyka olimpijska), s. 165, ISBN 978-83-7267-710-5 (pol.).
- ↑ Dowód ten jest przeredagowaną wersją dowodu zawartego w książce Wacława Sierpińskiego Wstęp do teorii liczb.
- ↑ Naoki Sato: Number Theory. s. 14–15. [dostęp 2009-06-03]. (ang.).
Linki zewnętrzne
- Eric W. Weisstein , Euler’s Totient Theorem, [w:] MathWorld, Wolfram Research (ang.). [dostęp 2024-02-02].