Str138

270 OdpowMn do ćwłcwrt

( ^h )

\ \2m f 1 J

I (Lak, że b

(* D/2

= I (moc! n)) oraz

I, a więc

w 25% przypadków.

18.    (a) (7(log³//logm); (b) 0 (log⁵//).

19.    (a) Liczba N jem złożona, gdyż n jest złożona (na podstawie wniosku

z twierdzenia 1.4.1); następnie podobnie jak w ćwiczeniu 9, przekonaj się, żc

8), więc także

¹ = 1 (mod A^;). Ale ponieważ Ar = — 1 (tnod iże = j. Zatem liczba N jest liczbą pseudopierwszą Eulera; z twierdzenia 5.1.5 wynika, żc jest także liczbą silnie pseudo

pierwszą.

(b) Użyj takiego samego rozumowania jak w ćwiczeniu 7(c).

20.    Jeśli zachodzi pierwsza możliwość w (3), to oczywiście (ć*)^f s 1 (mod ń). Przypuśćmy teraz, że b²'¹ = —1 (mod n). Niech k = 2^lj, gdzie liczba/jest nieparzysta. Jeśli i > r, to (b^k)* = 1 (mod //); jeśli i < r, to (ć*)^2r"‘'^r = (b^2ry = (- iy = -1 (mod n).

21.    (a) Wykaż, żc warunkami koniecznymi i wystarczającymi, które musi speł

17

niać b_y są:

1. Oba te warunki są spełnione w 25%

przypadków, tzn. dla 80 podstaw należących do (Z/561Z)*.

(b) Ponieważ ó⁷⁰ = 1 (mod 3) i (mod 11), więc 561 jest liczbą silnie pscu-dopierwszą przy podstawie b wtedy i tylko wtedy, gdy b^3S = ± 1 (mod 561), tzn. wtedy i tylko wtedy, gdy albo (i) b = 1 (mod 3), b = 1 (mod

17),

§1

11

11

= 1, albo (ii) b=—\ (mod 3), b=— 1 (mod 17),

— 1. Z chińskiego twierdzenia o resztach wynika, że istnieje

10 takich podstaw, 5 w przypadku (i) i 5 w przypadku (ii). Ośmioma nietrywialnymi podstawami b ±1 są: 50, 101, 103, 256, 305, 458,

460, 511.

22.    Skorzystaj z ćwiczenia 7(a), z podrozdziału 1.3, które mówi, że jedynymi pierwiastkami kwadratowymi z 1 są ±1.

23.    (a) 8² = 18² = — 1 (mod 65); 14² s 1 (mod 65), ale 14¹ # ±1 (mod 65).

(b) Przypadek, gdy liczba n jest potęgą liczby pierwszej, wynika z poprzedniego ćwiczenia, a więc załóżmy, że n nie jest potęgą liczby pierwszej. Po pierwsze, jeśli p\n i p = 3 (mod 4), to parzysta potęga żadnej liczby całkowitej nie przystaje do — 1 modulo n (gdyż — 1 nie jest resztą kwadratową modulo p)\ zatem w tym przypadku warunek, że liczba n jest silnie pseudopierwszą może być wypowiedziany następująco: b'=± \ (mod n). Ten warunek ma oczywiście własność multyplikaty-wności. Następnie załóżmy, że n = p®¹ ...p?^r, gdzie pj = 1 (mod 4) dla 1    < r. Niech ±aj będą dwoma pierwiastkami kwadratowymi z — 1

(mod pf^J) (pierwiastek kwadratowy modulo p*^J może być otrzymany

z pierwiastka kwadratowego modulo p_t\ por. ćwiczenie 12 z podroż* działu 2.2). Wtedy każda liczba h, która spełnia kongruencjc ±a_t (mod pV) (dla dowolnego wyboru znaku t) jest podstawą, przy której liczba n jest silnie pseudopierwszą, gdyż wtedy    -I

(mod ń). Wybierz b_{, przyjmując, że wszystkie +a_y M równe a_y, i wybierz ó₂, biorąc jakikolwiek z pozostałych 2^f - 2 układów znaków inny niż same plusy lub same minusy. Wtedy pokaż, źe dla b=*b_xb₂ mamy b^2t = 1 (mod ń) i b* = b $ ± 1 (mod ri).

24, (a) W tym przypadku otrzymasz liczbę c, różną od ±1, której kwadrat jest równy 1; wtedy NWDic + 1, n) jest nietrywialnym dzielnikiem liczby n.

(b) Wybierz p i q tak, aby p - 1 i q - 1 nie miały dużego wspólnego dzielnika (por. ćwiczenie 5 powyżej).

5.2

1.    NWD(x_s - x₃, n) = NWD(1\ - 63,91) = 7; 91 = 7 • 13.

2.    NWD(x₆ - *₃, n) = NWD(im - 26, 8051) = 97; 8051 = 83 • 97.

3.    AWZ>(*₉ - x₇, «) = NWD(m - 3397, 7031) = 79; 7031 = 79 • 89.

4.    AW0(*6 ~ *₃, n) = AW7)(630 - 112,2701) = 37; 2701 = 37 • 73.

5.    (a) Udowodnij przez indukcję względem k, że dla 1 < k ^ r prawdopodo

bieństwo tego, że wszystkie x_0l..., x_k_₁ są różne oraz x_k jest równy jednemu z wcześniejszych x_p wynosi 1/r. Dla k = 1 prawdopodobieństwo tego, że f(x₀) = x₀, jest równe 1/r. Krok indukcyjny przedstawia się następująco: z założenia indukcyjnego prawdopodobieństwo tego, że żadna z wcześniejszych liczb k nie była taka, że x_k = Xj dla pewnej

Zakładając to, stwier-

, . .    . ,    k-1 r-(k-1)

liczby j < k. wynosi 1--=-

r    r

^VA

r-(k

dzamy, że istnieje r — (k - 1) możliwych wartości f(x_k_ j), ponieważ funkcja różnowartościowa nie może przeprowadzić x_k__l na żadną z k — 1 wartośd f(xj), 0^j^k-2. Wśród tych r-(k -1) wartości jedną jest x₀, a wszystkie pozostałe są różne od x₀, x_v.... x_k_ _v Zatem szansa na to, że ta wartość jest jednym z wcześniejszych x_p wynosi l/(r — (k — 1)) (zauważ, że w tym przypadku j = 0). Prawdopodobieństwo tego, że zdarzą się obie meczy - żadna z wcześniejszych liczb k nie była pierwszą liczbą, dla której x_k = x₀, ale dla naszej liczby k zachodzi równość x_k = x₀ - jest iloczynem poszczególnych prawdopodobieństw,

czyli

I

Ir r - (k - 1) r (b) Ponieważ wszystkie wartości od 1 do r są jednakowo prawdopodobne,

wartością średnią jest - T k = - (r(r + 1)12) = (r+ l)/2.

r