34992 Str020 (2)

36    1. Kilka zagadnień element nrnc| lep fil liczb

równnnin liniowe w h/m7j rozwiązujemy, mnożąc obie strony równania przez odwrotność współczynnika przy niewiadomej.

Na ogół, gdy prowadzimy rozumowania „modulo m", pojęciem analo-gicznym do pojęcia „niczcrowy" jest „względnie pierwszy z m'\ Widzieliśmy powyżej, że kongruentne tak samo jak równania można dodawać, odejmować i mnożyć stronami (własność 3 kongruencji). Można je również dzielić, pod warunkiem, że „mianownik" jest względnie pierwszy z m.

Wniosek 3. Jeśli a = b (mod m), c = d (mod m) oraz NWD(c, m) = 1 (wtedy również NWD(d_i m) - 1), to ac~¹ = bd~¹ (mod m) (gdzie c~¹ id~^l oznaczają liczby odwrotne do c i d modulo m).

Dla dowodu wniosku 3 zauważmy, że

c(ac~¹ — bd~^l) = (acc~¹ — bdd~ ^l) = a — b = 0 (mod m),

a ponieważ c i m nie mają wspólnego dzielnika, więc m musi dzielić ac~^l — W¹.

Twierdzenie 1,3.2 (Małe twierdzenie Fermata). Niech p będzie liczbą pierwszą. Wtedy każda liczba a spełnia fcongruencję ap = a (mod p) i każda liczba a niepodzielna przez p spełnia kongruencję a^p ~¹ = 1 (mod p).

Dowód. Załóżmy najpierw, że pjfa. Po pierwsze twierdzimy, że liczby 0a, la, 2a. 3a,..., (/? — l)a tworzą pełny zbiór reszt modulo p. Aby się o tym przekonać, zauważmy, że w przeciwnym przypadku dwie z nich, powiedzmy ia i ja musiałyby być w tej samej klasie reszt, czyli ia = ja (mod p). To jednak oznacza, że p\(i — j)a, a ponieważ liczba a nie jest podzielna przez p, więcp\i — j. Liczby i oraz j są obie mniejsze od p, więc jest to możliwe tylko wtedy, gdy i = j. Stąd wynika, że liczby a, 2a,.... (p — 1 )a tworzą permutację liczb 1,2,..., p - 1, jeśli patrzymy na nie modulo p. Zatem iloczyn liczb pierwszego ciągu przystaje modulo p do iloczynu liczb drugiego ciągu, tzn. a^p~^l(p— 1)1 = s (p - 1)1 (mod p). Stąd wynika, że p\((p — 1)! (a^p_1 — 1)). Ponieważ liczba (p - 1)! nie jest podzielna przez p, więc p\(a^p~^l - 1), czego należało dowieść. Wreszcie, jeśli pomnożymy obie strony kongruencji a^p_1 = 1 (mod p) przez a, to otrzymamy pierwszą kongruencję dowodzonego twierdzenia, w przypadku gdy liczba a nie jest podzielna przez p. Ale jeśli liczba a jest podzielna przez p, to kongruencja a^p s a (mod p) jest trywialna, bo obie strony przystają do zera modulo p. To kończy dowód twierdzenia.

Wniosek. Jeśli liczba a nie dzieli się przez p i n = m (mod p — 1), to a" = a" (mod p).

Dowód wniosku. Przypuśćmy, że n> m. Ponieważ p — \ \n — m, więc mamy n = m + c(p - 1) dla pewnej dodatniej liczby całkowitej c. Mnożąc wtedy

kongruencję a^{9 1} & 1 (mod p) przez siebie e razy, a następnie przez cT-t? (mod p), otrzymamy żądany wynik: tf m <f (mod p).

Przykład 2. Znajdźmy ostatnią cyfrę liczby 2*⁰⁰⁰⁰⁰⁰ w systemie o podstawie 7.

Rozwiązanie. Niech p — 7. Ponieważ J 000000 daje resztę 4 przy dzieleniu przez /? — 1 = 6, więc mamy 2^1000000 s 2* = 16 = 2 (mod 7), czyli odpowiedzią jest 2.

Twierdzenie 1.3.3 (Chińskie twierdzenie o resztach). Przypuśćmy, ie chcemy rozwiązać układ kongruencji o różnych modułach:

x = a_l (mod mj, x = a₂ (mod m₂),

x = a_r (mod m_r).

Przypuśćmy następnie, że każde dwa moduły są względnie pierwsze: NWD(m_t, m.) = 1 dla i & j. Wtedy istnieje wspólne rozwiązanie x wszystkich tych kongruencji i każde dwa rozwiązania przystają do siebie modulo M = m_lm₂... m_r.

Dowód. Udowodnimy najpierw jednoznaczność modulo M (ostatnie zdanie). Przypuśćmy, że x' i xⁿ są dwoma rozwiązaniami. Niech x = x' — x". Wtedy x musi przystawać do 0 względem każdego modułu m„ a więc i modulo M (na podstawie własności 5 z początku tego podrozdziału). Następnie pokażemy, jak skonstruować rozwiązanie x.

Niech = M/m_l będzie iloczynem wszystkich modułów z wyjątkiem i-tego. Oczywiście NWD(m_t, M_t)— 1, a więc istnieje taka liczba N_t (którą można znaleźć za pomocą algorytmu Euklidesa), żeM_iN_i = 1 (mod mj). Przyjmijmy teraz x —    Af,iV,. Wtedy dla każdego i wszystkie składniki sumy poza

i

i-tym są podzielne przez gdyż nt_t\Mj dla j j* i. Zatem dla każdego i mamy: x = a_[M_iN_l = a_{ (mod m,), czego należało dowieść.

Wniosek. Funkcja Eulera q> jest „multyplikatywna”, tzn. q>(mń) — <p(m)(p(n), jeśli tylko NWD(m, ń) = 1.

Dowód wniosku. Musimy policzyć, ile jest liczb całkowitych zawartych między 0 i mn — 1 nie mających wspólnych dzielników z liczbą mn. Dla każdej liczby j z tego przedziału niech j\ będzie jej resztą z dzielenia przez m (tzn. 0    < m

oraz j=j_x (mod m)) i niech j₂ będzie jej resztą z dzielenia przez n (tzn.

0 śji < n oraz j = j₂ (mod «)). Z chińskiego twierdzenia o resztach wynika, że dla każdej takiej pary liczb j_it j₂ istnieje dokładnie jedna liczba j między