45430 Str019 (2)

34 1. Kiil>n zajMdnfed ekfnmtarnci lenni liczb

Przykład. Liczba pierwsza 12277 dzieli drugi czynnik iloczynu 20* + = (20⁷ + 1)(20⁴ - 20* -|- I). Znajdujemy więc Nł-T/.) (12277, 399 + 20/):

12277 « (31 - 2i)(399 + 20/) + (-132 + 178/),

399 + 20/ = (-1 - /X-132 + 178/) + (89 + 66/),

-132+ 178/ = (2/)(89 + 66/),

czyli największym wspólnym dzielnikiem jest 89 + 66/, a więc 12277 = * 89* + 66*.

(a)    Wykorzystując równość 19⁶ + 1 = 2 • 13² • 181 • 769 i algorytm Euklidesa dla liczb całkowitych Gaussa, przedstaw 769 jako sumę dwóch kwadratów.

(b)    Podobnie, przedstaw liczbę pierwszą 3877, która jest dzielnikiem 15⁶ + 1 jako sumę dwóch kwadratów.

(c)    Przedstaw liczbę pierwszą 38737, która jest dzielnikiem 2³⁶ + 1, jako sumę dwóch kwadratów.

1.3. Kongruencje

Podstawowe własności. Dla danych trzech liczb całkowitych a, b i m mówimy, że „liczba a przystaje do liczby b modulo m” i piszemy a = b (mod m), gdy różnica a — b jest podzielna przez m. Liczbę m nazywamy modułem kon-gruencji. Następujące własności relacji kongruencji wynikają bezpośrednio z definicji:

1. (i) a = a (mod m); (ii) a = b (mod m) wtedy i tylko wtedy, gdy { b = fl(modm); (iii) jeśli a = b (mod m) oraz b = c (mod m), to | a = c(modm). Dla ustalonej liczby m z własności (i)—(iii) wynika, że rela- 2 cja kongruencji modulo m jest relacją równoważności.

2.    Dla ustalonej liczby m każda klasa równoważności ze względu na relację . kongruencji modulo m ma dokładnie jednego reprezentanta wśród liczb od > 0 do m— 1. (Jest to inny sposób powiedzenia tego, że każda liczba przystaje modulo m do dokładnie jednej liczby zawartej między 0 i m — 1.) Zbiór klas ; równoważności (zwanych klasami reszt modulo m) będzie oznaczany przez Z/mZ. Każdy zbiór reprezentantów klas reszt modulo m będzie nazywany \ pełnym zbiorem reszt modulo m.

3.    Jeśli a = b (mod m) i c = d (mod m), to a ± c == b ± d (mod m) oraz ac = bd ■ (mod m). Inaczej mówiąc, kongruencje (względem tego samego modułu) ; można dodawać, odejmować i mnożyć stronami. Okazuje się też, że zbiór i klas równoważności Z/mZ jest pierścieniem przemiennym, tzn. klasy reszt można dodawać, odejmować i mnożyć (wynik przy tym nie zależy od wyboru reprezentantów z tych klas) i działania te spełniają zwykłe aksjomaty (przemienność, łączność, posiadanie elementów przeciwnych itp.).

4.    Jeśli a a# h (mod m), to a *? b (mod d) dla karlego dzielnika d\m.

5.    Jeśli a = b (mod m), a - b (mod n) oraz nin vi względnie pierwsze, to a == ó (mod mn). (Por. własność 5 relacji podzielności w podrozdziale 1.2.)

Twierdzenie 1.3.1. Elementami Z/mZ mającymi elementy odwrotne ze względu na mnożenie są klasy liczb względnie pierwszych z m, tzn. liczbami a, dla których istnieje liczba b taka, ze ab s 1 (mod m), są dokładnie te liczby a, dla których NWD(a, m) = 1. Ponadto, jeśli NWD(a, ni) — 1, to taka liczba odwrotna b może być znaleziona za pomocą 0(log³m) operacji na bitach.

Dowód. Po pierwsze, jeśli d = NWDia, w) jest większy od 1, to dla żadnego b nie może być ab & 1 (mod m), ponieważ wtedy liczba d dzieliłaby ab - 1, a więc dzieliłaby 1. Na odwrót, jeśli NWDia, m) = 1, to na mocy własności 2 powyżej możemy założyć, że a < m. Wtedy z twierdzenia 1.2.2 wynika, że istnieją liczby u i u, które mogą być znalezione za pomocą 0(log³m) operacji na bitach, takie że ua + vm = 1. Dla b = u otrzymamy m 11 — ua = 1 — aó, czego należało dowieść.

Uwaga. Jeśli NWD{a, m) = 1, to definiujemy ujemną potęgę a"" mod m jako n-tą potęgę klasy reszt odwrotnej do a; jest ona reprezentowana przez n-tą potęgę dowolnej liczby b, dla której ab = 1 (mod m).

Przykład 1. Znajdźmy 160“¹ mod 841, tzn. odwrotność liczby 160 modulo 841.

Rozwiązanie. Z ćwiczenia 6(c) w ostatnim podrozdziale wynika, że odpowiedzią jest 205.

Wniosek 1. Jeżeli p jest liczbą pierwszą, to każda niezerowa klasa reszt ma element odwrotny ze względu na mnożenie, przy czym można go znaleźć za pomocą O (log³/?) operacji na bitach. Mówimy, że pierścień Z/pZ jest ciałem. To „p-elementowe ciało ” często oznaczamy przez F_.

Wniosek 2. Przypuśćmy, że chcemy rozwiązać kongruencję liniową ax = b (mod m), przy czym bez straty ogólności możemy założyć, że Oś a, b <m. Wtedy, jeśli NWD{a, m) = 1, to istnieje rozwiązanie x₀, które można znaleźć za pomocą 0(log³m) operacji na bitach; wszystkie inne rozwiązania są postaci x = x₀ + mn dla pewnej liczby całkowitej n. Następnie przypuśćmy, że d = NWD(a, m). Wówczas istnieje rozwiązanie wtedy i tylko wtedy, gdy d\b i w tym przypadku kongruencja jest równoważna (tzn. ma takie same rozwiązania) kongruencji a'x = b' (mod m^r), gdzie a' = a/d, b' = b/d, m' = mjd.

Pierwszy wniosek jest szczególnym przypadkiem twierdzenia 1.3.1. Drugi wniosek łatwo można wyprowadzić z twierdzenia 1.3.1 i z definicji. Podobnie jak w znanym przypadku równań liniowych w zbiorze liczb rzeczywistych,