Twierdzenie Eulera (teoria liczb)

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do 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 i są liczbami względnie pierwszymi, to dzieli liczbę gdzie oznacza wartość funkcji Eulera, czyli liczbę tych liczb całkowitych dodatnich nie większych od które są z względnie pierwsze.

Innymi słowy, zachowując powyższe oznaczenia,

Słabszą wersją tego twierdzenia jest małe twierdzenie Fermata.

Przykład[edytuj | edytuj kod]

Mamy – np. liczby są względnie pierwsze z ( jest liczbą pierwszą, ), dlatego też liczby itd. są podzielne przez

Dowód[1][edytuj | edytuj kod]

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:

  1. dla każdej liczby gdzie zachodzi i jest względnie pierwsza względem (czyli ),
  2. funkcja opisana wzorem gdzie jest różnowartościowa (wtedy zbiory i byłyby równoliczne, gdyż jest z definicji suriekcją),

bowiem zbiory i 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[2][edytuj | edytuj kod]

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:

,
,
.

q.e.d.

Przypisy[edytuj | edytuj kod]

  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.). s. 14–15. [dostęp 2009-06-03].