52660 Str024 (2)

44 I. Kilka ngadnleń rlwnrnlnrncj teorii Itab

23.    (a) Wykorzystaj twierdzenie o rozkładzie na czynniki pierwsze do dowodu tego, żc iloczyn

wjaklt liecy |un>uc f | _ —

P

jest rozbieżny do nieskończoności.

(b)    Korzystając z części (a), udowodnij, że szereg odwrotności liczb pierwszych jest rozbieżny.

(c)    Znajdź ciąg rtj rozbieżny do nieskończoności, dla którego

lim ^ = I i ciąg n,, dla którego lim    = 0.

ftj    J-*eo flj

24.    Niech N będzie niezwykle dużą tajną liczbą całkowitą używaną do uruchamiania systemu rakiet bojowych, tzn. osoba znająca tę liczbę N mogłaby odpalić rakiety. Przypuśćmy, że mamy do dyspozycji generała-głównodo-wodzącego oraz n generałów niższych stopni. Na wypadek, gdyby gene-ral-głównodowodzący (który zna liczbę N) okazał się niezdolny do działania, chcemy by generałowie niższych stopni mieli wystarczająco dużo informacji częściowych o liczbie N tak, by dowolnych trzech z nich (ale żadnych dwóch) mogło wspólnie uruchomić system.

(a)    Niech p_lt ..., p_H będą różnymi liczbami pierwszymi, większymi od IZM, ale znacznie mniejszymi od -JN. Korzystając z liczb p_lt opisz częściowe informacje o liczbie N, które mogą być przekazane generałom niższych stopni.

(b)    Uogólnij ten system na sytuację, w której dowolnych k (k > 2) generałów niższych stopni może wspólnie uruchomić system (ale żadnych k — 1 nie może uruchomić systemu). Takie rozwiązanie nazywa się k-progowym systemem dzielenia się tajemnicą.

1.4. Zastosowania do problemu rozkładu na czynniki

Twierdzenie 1.4.1. Dla dowolnej liczby całkowitej b i dowolnej dodatniej liczby całkowitej n liczba bⁿ — 1 jest podzielna przez 6—1, przy czym iloraz jest równy łf~^l + 6"~² -ł-... + 6² + 6 + 1.

Dowód. Możemy skorzystać z tożsamości dotyczącej wielomianów, wynikającej z następującej uwagi: liczba 1 jest pierwiastkiem wielomianu x" — 1, więc wielomian x" — 1 musi być podzielny przez dwumian x — l. Dokładniej, dzielenie wielomianów pokazuje, że x? — \ = (x — |||pM -ł- xP~² + ... +

-ł- x² + x + 1). (Tę tożsamość możemy też wyprowadzić, mnożąc wielomian x"^_1 4- x"^-2 + ... + x² + x+ 1 przez x i odejmując xⁿ~¹ + x?~² + ... +

+ x* + x+\ , co po redukcji wyrazów podobnych daje x" — 1). Teraz otrzymujemy dowód twierdzenia, podstawiając b w miejsce x.

Inny dowód wykorzystuje system pozycyjny o podstawie b. Liczba tf — I zapisana w systemie o podstawie b składa się z n cyfr b ~ 1 (np. 10⁶ ~ 1 = 999999). Z drugiej strony liczba lf~' + łf² + ... + b¹ + b + 1 składa się z n jedynek. Mnożąc 11 J...JJ1 przez liczbę jednocyfrową 6-1, uzyskamy w wyniku ((6 — 1)(6 - 1)(6 — 1)...(6 - \)(b - 1)(6 - 1))$ = 6" — J.

Wniosek. Dla każdej liczby całkowitej b i dowolnych liczb całkowitych dodatnich m i n zachodzi równość

tr-\={ir-1)(6"^~^l) + łr'*'^t) +... + ó^2- ir +1).

Dowód. Wystarczy podstawić 6" w miejsce 6 w ostatnim twierdzeniu.

Jako przykład zastosowania tego wniosku, zobaczmy, że liczba 2³⁵ — 1 jest podzielna przez 2⁵ — 1 = 31 i przez 2⁷ - 1 = 127. Mianowicie wystarczy przyjąć 6 = 2 oraz m = 5 \ n = 1 \ub m = l i n = 5.

Twierdzenie 1.4.2. Niech liczba 6 będzie względnie pierwsza z liczbą m i niech a i c będą liczbami całkowitymi dodatnimi. Jeśli 6* = 1 (mod m), b^c = 1 (mod m) oraz d = NWD(a, c), to b^d s 1 (mod m).

Dowód. Korzystając z algorytmu Euklidesa, możemy przedstawić liczbę d w postaci kombinacji liniowej ua + vc, gdzie u i u są liczbami całkowitymi. Łatwo zauważyć, że jedna z liczb u i o jest dodatnia, a druga - ujemna hib równa zeru. Bez straty ogólności możemy przyjąć, że u > 0, v < 0. Teraz podnosimy obie strony kongruencji 6* = 1 (mod m) do potęgi u oraz podnosimy obie strony kongruencji 6^C= 1 (mod m) do potęgi —d. Dzieląc jedną kon-gruencję przez drugą, otrzymamy 6“^-c(-p) = 1 (mod m). Ale au + cv = d, co kończy dowód twierdzenia.

Twierdzenie 1.4.3. Jeśli p jest dzielnikiem pierwszym liczby 6"- 1, to albo (i) p\b^d — 1 dla pewnego właściwego dzielnika d liczby n, albo (ii)p = 1 (mod n). Jeślip > 2 i liczba n jest nieparzysta, to w przypadku (ii) mamy p= 1 (mod 2n).

Dowód. Mamy 6" = 1 (mod p) oraz 6^P“¹ = 1 (mod p) na mocy małego twierdzenia Fermata. Z poprzedniego twierdzenia wynika, że wtedy 6* s 1 (mod p\ gdzie d = NWD(n, p - 1). Jeżeli d < n, to mamy p\b⁴ - 1 dla pewnego właściwego dzielnika d liczby n, czyli zachodzi przypadek (i). Z drugiej strony, jeśli d = n, to d\p — 1, a więc p = 1 (mod ń). Wreszcie, jeśli pin są obie nieparzyste i n\p — 1 (tzn. zachodzi przypadek (ii)), to oczywiście 2n\p— 1.

Teraz pokażemy, w jaki sposób to twierdzenie może być wykorzystane do faktoryzacji (czyli rozkładu na czynniki) pewnych typów dużych liczb całkowitych.