Twierdzenie Eulera (teoria liczb)

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

Treść twierdzeniaEdytuj

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ładEdytuj

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:

 
 
 

q.e.d.

PrzypisyEdytuj

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