Str023 (2)

42 I. Kilki ngadnifri elementarnej teorii llorb

6.    Do wyłożenia kafelkami podłogi o wymiarach 8x9 stóp kupiłeś 72 ka-fclki, ich ceny jednak nie pamiętasz. Na rachunku (który podaje cenę nie opodatkowaną) widnieje jakaś suma poniżej 100 8, ale pierwsza i ostatnia cyfra są nieczytelne. Możesz odczytać 70,6?$. Ile kosztowały kafelki?

7.    (a) Przypuśćmy, że liczba m jest albo potęgą p^a liczby pierwszej p > 2, albo

podwojoną potęgą nieparzystej liczby pierwszej. Udowodnij, że jeśli v² = 1 (mod m), to albo x = 1 (mod m), albo x s — 1 (mod m).

(b)    Udowodnij, że własność (a) nic zachodzi, gdy liczba m nie jest postaci p* lub 2p^m oraz m # 4.

(c)    Udowodnij, że jeśli m jest liczbą nieparzystą podzielną przez r różnych liczb pierwszych, to kongrucncja x² = 1 (mod m) ma 2^r różnych rozwiązań zawartych między 0 i m.

8.    Udowodnij twierdzenie Wilsona, które mówi, że dla dowolnej liczby pierwszej p zachodzi kongrucncja: [p — 1)! = — 1 (mod p). Udowodnij, że (n — 1)! nie przystaje do — 1, gdy liczba n me jest pierwsza.

9.    Znajdź liczbę trzycyfrową (w systemie dziesiętnym), która daje resztę 4 przy dzieleniu przez 7, 9 i 11.

10.    Znajdź najmniejszą liczbę całkowitą dodatnią, która daje resztę 1 przy dzieleniu przez 11, resztę 2 przy dzieleniu przez 12 i resztę 3 przy dzieleniu przez 13.

11.    Znajdź najmniejsze rozwiązania nieujemne następujących układów kon-grucncji:

(a)    x s 2 (mod 3) x s 3 (mod 5)

* = 4 (mod 11) x = 5 (mod 16)

(b)    x s 12 (mod 31) x = 87 (mod 127) x = 91 (mod 255)

(c)    19* = 103 (mod 900)

10xs 511 (mod 841)

12.    Przypuśćmy, że liczba dodatnia trzycyfrowa (w systemie dziesiętnym) dająca resztę 7 przy dzieleniu przez 9 i przez 10 oraz resztę 3 przy dzieleniu przez 11 jest dzielnikiem liczby sześciocyfrowej, która daje resztę 8 przy dzieleniu przez 9, resztę 7 przy dzieleniu przez 10 i resztę 1 przy dzieleniu przez 11. Znajdź iloraz.

13.    W sytuacji z twierdzenia 1.3.3, załóżmy, że 0 < a_i < m_j < B dla wszystkich j, gdzie B jest pewnym dużym ograniczeniem górnym wszystkich modułów. Przypuśćmy, że liczba r też jest duża. Oszacuj liczbę operacji na bitach potrzebnych do rozwiązania układu kongruencji. Twój wynik powinien zależeć od B i r oraz powinien dopuścić taką możliwość, że liczba r jest bardzo duża albo że jest bardzo mała w porównaniu z liczbą cyfr liczby B.

14.    Użyj metody iterowanego podnoszenia do kwadratu, by obliczyć wartość 38^7S mod 103.

15.    Czy metoda iterowanego podnoszenia do kwadratu oszczędza czas, gdy chcemy znać wszystkie cyfry potęgi (a nie tylko resztę z dzielenia przez ustaloną liczbę)? Wyjaśnij to, używając oszacowań w notacji O.

16.    Zauważ, że dla liczb a względnie pierwszych z p, liczba a⁹'¹ jest liczbą odwrotną do a modulo p. Przypuśćmy, że liczba p jest bardzo duża. Porównaj wykorzystanie metody iterowanego podnoszenia do kwadratu do obliczenia a⁹'² z algorytmem Euklidesa jako efektywnych metod znajdowania a~¹ mod />, gdy (a) liczba a ma prawie tyle samo cyfr co p i (b) gdy liczba a jest znacznie mniejsza od p.

17.    Oblicz <p(ń) dla wszystkich n od 90 do 100.

18.    Sporządź listę wszystkich liczb n, dla których ę(ń) < 12, i udowodnij, że ta lista zawiera wszystkie takie liczby.

19.    Przypuśćmy, że liczba n nie jest pełnym kwadratem i że n— 1 > > (p(ń) > n — n^2,i. Udowodnij, że n jest iloczynem dwóch różnych liczb pierwszych.

20.    Udowodnij, że jeśli m ^ 8 jest potęgą 2, to wykładnik potęgi w twierdzeniu 1.3.5 może być zastąpiony przez <p(m)l2.

21.    Niech

m = 7785562197230017200 =

= 2⁴ ■ 3³ • 5² • 7 • 11 ■ 13 • 19 • 31 • 37 • 41 • 61 • 73 • 181.

(a)    Oblicz resztę z dzielenia 6647³⁶² przez m.

(b)    Niech a będzie liczbą dodatnią mniejszą od m, względnie pierwszą z m. Najpierw znajdź dodatnią potęgę liczby a mniejszą niż 500, która jest odwrotnością a modulo m. Następnie opisz algorytm znajdowania tej potęgi liczby a, jeżeli wykonuje się działania modulo m. Ile mnożeń i dzieleń trzeba wykonać, by obliczyć tę potęgę? (Dzielenie przez m jest traktowane jako jedno działanie). Jaką maksymalną liczbę cyfr (w systemie dwójkowym) będą miały liczby pojawiające się w obliczeniach? Na końcu podaj dobre oszacowanie liczby operacji na bitach potrzebnych do znalezienia a~¹ mod m za pomocą tej metody. (Twoja odpowiedź powinna być konkretną liczbą - nie używaj tu notacji O.)

22.    Podaj inny dowód twierdzenia 1.3.7 opierający się na następującym rozumowaniu. Dla każdego dzielnika d liczby n, niech S_d oznacza podzbiór (jest to tzw. „podgrupa”) zbioru Z/nZ składający się ze wszystkich wielokrotności n/d. Zatem zbiór S_d ma d elementów.

(a)    Udowodnij, że S_d ma cp(d) różnych elementów x, które generują S_d, tzn. takich, że wielokrotności x (brane modulo n) wyczerpują wszystkie elementy S_d.

(b)    Udowodnij, że każdy element zbioru Z/nZ generuje jeden zbiór S_d, a więc liczba elementów zbioru Z/nZ jest równa sumie (ze względu na wszystkie dzielniki d) liczb elementów, które generują S_d. Razem z częścią (a) daje to dowód twierdzenia 1.3.7.