42759 Str127

250    Odpowiedzi do ćwiczeń

22. (a) Pokaż, żc jeśli x == j • ”, to ..v generuje Ą wtedy i tylko wtedy, gdy d

NIVD(x. d) = 1. Zauważ, żc_/ przebiega liczby 0, 1, .... rf — 1.

(b) Podziel zbiór Z/wZ na podzbiory zgodnie z tym, który zbiór Ą dany element generuje. Zgodnie z (a), podzbiór odpowiadający danemu Ą ma elementów.

P

23. (a) Rozwiń każdy czynnik iloczynu w szereg geometryczny: ( 1 H—- +

P P J

składników będą wszystkimi możliwymi iloczynami postaci

^—2 + —y + ...]. Po otwarciu wszystkich nawiasów mianowniki

pppP-P?*- Z twierdzenia o istnieniu i jednoznaczności rozkładu na czynniki pierwsze wynika, że każda liczba naturalna dodatnia n wystąpi dokładnie raz jako taki mianownik. Zatem cały iloczyn jest rów-

® 1

ny sumie szeregu harmonicznego Y —, który jest rozbieżny.

(b) Udowodnij najpierw, że dla ;c < — mamy * > — — log(l — jc) (przyjrzyj się wykresowi funkcji logarytmicznej). Podstaw at = — i porównaj

P

Yj~^z logarytmem iloczynu z punktu (a).

(c) Dla dowolnego ciągu liczb pierwszych n rozbieżnego do nieskończono-, .    ę»(/*)    1

sci mamy-— 1---► 1; dla dowolnego ciągu liczb n podziel-

R    ZZ

nych przez coraz więcej kolejnych liczb pierwszych (na przykład weź

= 0, na mocy (a).

24. (a) Przekaż liczbę p, oraz resztę z dzielenia iV przez p, /-temu generałowi, a następnie skorzystaj z chińskiego twierdzenia o resztach.

P? Wybierz p_t tak, by każde p_t było większe niż i znacznie mniejsze niż ^k~y/N.

1.4

3.    Przeprowadź to samo rozumowanie co w dowodzie ostatniego twierdzenia (1.4.3), by wykazać, że ±1 (mod m). Ale ponieważ (b^d)^a,d= — 1 (mod m), więc b^d = -1 (mod m) i liczba a/d jest nieparzysta.

4.    Skorzystaj z ćwiczenia 3 dla a — n i c = (p — l)/2.

5.    (a) 2⁸ + 1 = 257; (b) skorzystaj z ćwiczenia 4; (c) m = 97 ■ 257 • 673.

6.    2- il²* 13 *4561,2⁵ * 5 - 7 • 13 * 41 * 73 * 6481.

7. 2* *3²'7* 13'31 *601.

g’ 3² • 41 • 271, 3* • 7 * II • 13 • 37,3² • 11 • 73'101 * 137.

9.    7 • 23 • 89 • 599479; 7^Z • 127 • 337 (ten przykład pokazuje, że jeśli w twierdzeniu 1.4.3 p jest liczbą pierwszą i p\h* - 1, to liczba bⁿ - 1 może być podzielna przez wyższą potęgę p niż liczba b⁴ - 1).

10.    7 -31 151, 3²* 7-11 -31 *151 *331,

3² • 5² • 7 • 11 • 13 * 31 • 41 • 61 • 151 * 331 • 1321.

11.    (a) Przeprowadź obok siebie obliczenia NWD(a^m - 1, a” - 1) i NWD(m,

n) za pomocą algorytmu Euklidesa. Zauważ, że w każdym kroku reszta otrzymana w pierwszym obliczeniu jest postaci a^r - 1, gdzie r jest resztą otrzymaną w drugim obliczeniu. Na przykład w pierwszym kroku dzielimy a^m - 1 przez a" - 1, by otrzymać resztę o' - 1, gdzie r jest resztą z dzielenia m przez n.

(b) Z (a) i chińskiego twierdzenia o resztach wynika, że żadne dwie liczby między 0 i f](2^m‘ - 1) nie mają tego samego zbioru reszt. Ten iloczyn jest większy niż 2^,ł/2 > l⁷* > ab. Mnożymy przez siebie r razy liczby co najwyżej /- bitowe, co daje oszacowanie czasu rzędu 0(rl²) = O (ki). Jest to oszacowanie r razy lepsze od oszacowania czasu zwykłego mnożenia liczb a i b (które wymaga czasu rzędu 0(k²)).

2.1

1.    Liczba pierwsza p    2    3    5    7    11    17

Najmniejszy generator    1    2    2    3    2    3

Liczba generatorów    1    1    2    2    4    8

2.    (a) Jeśli g^p~¹ = 1 (mod p²\ to zastąp g przez (p + \)g i pokaż, że wtedy

g^p~^l = 1 + g_xp, gdzie liczby g_i i p są względnie pierwsze. Teraz, jeśli g^J = 1 (mod p^a), to najpierw pokaż, że p - \\j, tzn. j=(p- l);_łt a więc (1 + gj>)^il = 1 (mod />*). Ale pokaż, że (1 + g_lp)^h = 1 + +j_xg_xp + wyższe potęgi p, a zatem p^a~^l musi dzielić j_x.

(b) Dla dowodu pierwszej części zob. ćwiczenie 20 do podrozdziału 1.3; dowód drugiej części (który sprowadza się do wykazania, że 5^j nie może przystawać do 1 modulo 2^a, chyba że 2®“² |y) jest podobny do dowodu części (a).

3.    5⁶.

4.    2 dla d = 1: Af, Af + 1; 1 dla d= 2: Af² + Af +1; 2 dla d= 3: Af³ + Af² + 1, Af³ + Af+1; 3 dla d = 4: A^r4 + AT³ + 1, A^ + AT+1, X* + AT³ + AT² + + AT+1; 6 dla d = 5: A^ + A^ + l, AT⁵ + Af² + 1, X⁵ + X⁴ + X³ + + X² + 1, X⁵ + X* + AT³ + X+ 1, AT³ + AT⁴ + Af² + AT+ 1, AT⁵ + A* + + Af² + AT+1; 9 dla d = 6: AT⁶ + AT* + 1, AT⁶ + Af³ + 1, X⁶ + X+ 1, X⁶+X⁵+X⁴+X²+1, X⁶+X⁵+A?⁴+AT+1, X⁶ + X⁵ + AT³ + X¹ +1, ^⁶+Ar³-ł-A^r2+A'+i,A^,6+A^,4+A'³+Ar+i,Ar⁶+jr⁴+Ar²+Ar+i.