54830 Str084

Dowód utwierdzenia. Ponieważ b^,n 1,/J — b¹' ' — — i (tnod n), więc podnosząc obie strony do potęgi t otrzymamy    = — 1 (mod n). Ponieważ p\n, ta

sama kongrucncja zachodzi modulo p. Ale gdybyśmy mieli s' < s, to liczba b¹' ' nic przystawałaby do I modulo p, co przeczyłoby małemu twierdzeniu

1 (mod n)

Fermata. Zatem .r' > s. Jeśli s' = x, to kongruencja (b²' ¹ )'

fjip- i)/a _ [ji‘ ~'t‘ = _ j (_mod p). Natomiast, jeśli s¹ > s, to ta sama kongrucncja podniesiona do potęgi 2‘ ~‘ implikuje, że To kończy dowód stwierdzenia.

Powracamy teraz do dowodu twierdzenia 5.1.6 w przypadku (ii). Zapisujemy liczbę n w postaci iloczynu liczb pierwszych (niekoniecznie różnych): n = fjp. Niech k oznacza liczbę czynników p takich, że s' = s, gdy zapiszemy liczbę p — 1 w postaci p — 1 — 2*' t' z nieparzystą liczbą t' (w liczbie k uwzględniamy czynnik pierwszy p wraz z jego krotnością, tzn. a razy, jeśli p* || ń).

(-1)*.

implikuje, że

(})

mm

Zgodnie ze stwierdzeniem mamy zawsze s' > s oraz

Jednakże, wykonując działania modulo 2*⁺¹, widzimy, że p = 1, chyba że p jest jedną z k liczb pierwszych, dla których s' = s, wtedy p = 1 +2^a. Ponieważ n = 1 + 2¹/ =1+2* (mod 2^a + 1), mamy 1 + 2' = Y\p = (1 + 2¹)* = s i + k2^a (mod 2* + 1) (przy czym ostatni krok wynika ze wzoru dwumianowego). To oznacza, że liczba k musi być nieparzysta i stąd [—J = (—1)* = = — 1, czego należało dowieść.    \ⁿ /

Przypadek (iii). W końcu przypuśćmy, że ó²'^-1* = — 1 (mod ń) dla pewnej liczby r takiej, że 0 <r <s. (Piszemy r — 1 zamiast r w (3)). Ponieważ wtedy b^{n~^1)l2 = 1 (mod n), musimy pokazać, że w przypadku (iii) mamy

— 1. Niech znówp będzie dowolnym dzielnikiem pierwszym liczby n i zapiszmy p — 1 w postaci p — 1 = 2 'V, gdzie liczba /'jest nieparzysta.

Stwierdzenie. Zachodzi nierówność s' > r oraz równość

1,    jeżeli s' = r,

1,    jeżeli .s' > r.

Dowód tego stwierdzenia jest taki sam jak dowód poprzedniego stwierdzenia w przypadku (ii).

Aby dowieść twierdzenia w przypadku (iii), oznaczymy przez k liczbę czynników pierwszych p (niekoniecznie różnych) w iloczynie « = ]"]p, dla których zachodzi pierwsza możliwość, tzn. s' = r. Wtedy, tak jak w przypadku

(ii), oczywiście mamy ( -- ) = (-1)*. Jednakże ponieważ n = 1 + 2^at m 1 5,1. Uchy pWdopterwtrt 165

._Tl0Cl 2'^łi) oray,« = | [p = (1 -f 2')* (mod 2'⁴¹), więc stąd wynika, it liczba jtmusi być parzysta, czyli j * 1. To kończy dowód twierdzenia 5.1.6.

Zanim przeprowadzimy dowód twierdzenia 5.1.7, udowodnimy ogólny lemat dotyczący liczby rozwiązań równania x^k = I w „grupie cyklicznej* zawierającej m elementów. Spotkaliśmy już raz ten lemat na początku podroż-działu 2.2; warto porównać dowód tego lematu z dowodem twierdzenia 2.2.1.

Lemat 1. Niech d = NWD(k, ni). Wtedy istnieje dokładnie d elementów grupy (g. g²» S³» •••» S" “ U spełniających równanie x^k = 1.

Dowód. Element g^j spełnia to równanie wtedy i tylko wtedy, gdy g* = 1, to

znaczy wtedy i tylko wtedy, gdy m\jk. Jest to równoważne: - co z kolei

d d

jest równoważne temu, żey jest wielokrotnością mjd, gdyż mjd i kjd są względnie pierwsze. Istnieje d takich wartości j, 1 < j ^ m. To kończy dowód lematu.

Potrzebujemy jeszcze jednego lematu, którego dowód* jest podobny do dowodu lematu 1.

Lemat 2. Niech p będzie nieparzystą liczbą pierwszą i niech p - I = 2'V. gdzie /' jest liczbą nieparzystą. Wtedy liczba tych xe(Z/pZ)*, które spełniają kon-gruencję x^Vt = -1 (mod p) (gdzie / jest liczbą nieparzystą), jest równa 0, gdy r £ s' i jest równa V • NWD{t, /'), gdy r < j'.

Dowód. Niech g będzie generatorem grupy (Z/pZ)* i zapiszmy x w postaci g^J, gdzie 0    < p — 1. Ponieważ g°^,“^1)/2 s -1 (mod p) oraz p -1 = 2'V, kon

gruencja z tezy lematu jest równoważna następującej kongruencji: 2^rtj = 2*'"V (mod 2*V) (z niewiadomą/). Oczywiście nie istnieje rozwiązanie, gdy r > s' - 1. W przeciwnym razie dzielimy obie strony przez największy wspólny dzielnik modułu i współczynnika przy niewiadomej, tzn. przez 2^rd, gdzie d = NWD(t, t'). Otrzymana kongruenqa ma tylko jedno rozwiązanie /' . . .

modulo 2* "^r • —- ima 2 ^rd rozwiązań modulo V i\ czego należało dowieść. To kończy dowód lematu 2.

Dowód twierdzenia 5.1.7. Przypadek (i). Załóżmy najpierw, że liczba n jest podzielna przez kwadrat pewnej liczby pierwszej p. Na przykład p*!i n, a > 2. Pokażemy, że w tym przypadku n nie może być nawet liczbą pseudopierwszą (tym bardziej liczbą silnie pseudopierwszą) dla więcej niż (n - l)/4 podstaw b, 0 <b <n. W tym celu przypuśćmy, że ó"“^ł = 1 (mod n), skąd wynika, że ó"'¹ = 1 (mod p²). W ten sposób znaleźliśmy warunek modulo p², który liczba b musi spełniać. Przypomnijmy, że (Z/p²Z)* jest grupą cykliczną rzędu Pip — 1) (por. ćwiczenie 2 w podrozdziale 2.1), tzn. istnieje taka liczba g, że