276062006

14 Podstawy teorii liczb

1.7 Małe twierdzenie Fermata i twierdzenie Eulera

Zaczniemy od sformułowania tzw. ” Małego Twierdzenia Fermata”, którego w tym momencie dowodzić nie będziemy, ale któremu (wraz z wybranymi dowodami) poświęcimy osobną opowieść w aneksie. W tej chwili wykorzystamy fakt, że dziś możemy na niego patrzeć jak na wniosek z ogólniejszego twierdzenia Eulera, choć historycznie rzecz ujmując to MTF było pierwszą udowodnioną własnością. Więcej o tym ” małym” wielkim twierdzeniu poczytać można w rozdziale C.6

Twierdzenie 1.7.1 (Małe twierdzenie Fermata=MTF). Jeśli p - liczba pierwsza, k € Z to (1) Jeśli k jest wzgędnie pierwsza z p, to k^p~^l = 1 (mod p) (2) k^p = k(mod p).

Uogólnieniem powyższej własności jest następne Twierdzenie Eulera (nazywane też Twierdzeniem Eulera-Fermata), które wykorzystuje wprowadzone wcześniej pojęcie funkcji Eulera.

Twierdzenie 1.7.2 (Twierdzenie Eulera). Jeśli m E N, k E Z - względnie pierwsza z m, to k^ = 1 (mod m).

Dowód. Jest to oczywiste gdy m = 1, wobec tego załóżmy, że m > 1.

Niech I := {j E [0,m) : NWD(j,m) = 1}. Wówczas #/ = <p(m).

Jeśli j jest liczbą względnie pierwszą z m, to także kj ma tę własność. Dla każdego j E I istnieje 0 < r,- < m takie, że kj = rrujj+rj, dla pewnego qj. Oczywiście z tej równości wynika, że r₃- E I. Zauważmy, że

I 3 j —* rj E I

jest bijekcją. Istotnie dla i < j ze zbioru I reszty rj, rj muszą być różne, gdyż w przeciwnym wypadku k(j — i) = m(qj — ę,), czyli k(j — i) byłoby podzielne przez m - sprzeczność.

Wobec tego 2 = II J ⁼ El ^rj i jest to liczba względnie pierwsza z m. Otrzymujemy w jei jei

ten sposób układ <p{m) kongruencji kj = r'j(mod m).

Mnożąc stronami kongruencje kj = rj(mod m) dla wszystkich j E I dostajemy:

*«’(">) z = z(mod p)

gdzie 2 jest iloczynem wszystkich liczb całkowitych z I. Ale 2 jest względnie pierwsza z m, skąd z własności kongruencji mamy k^^m^ = l(mod m).    □

Jak widać, jeśli m jest liczbą pierwszą jak w Twierdzeniu Fermata, dostajemy dokładnie tezę tego twierdzenia, gdyż <p(m) wtedy jest równe m— 1.    □