Twierdzenie Eulera (teoria liczb)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Twierdzenie Eulera o liczbach względnie pierwszych to twierdzenie teorii liczb, które mówi, co następuje:

Treść twierdzenia[edytuj]

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]

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

Dowód[1][edytuj]

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]

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:

QED.

Przypisy

  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.). [dostęp 03.06.2009]. s. 14-15.