19016 Str130

»Sł MpdwMn do ćwfcwrt

Ponieważ 2^,fc» I (mod p)> możesz wykazać, że NWD((p — I j/2*, 2*) --- 2\ skąd natychmiast wynika, te p m I (mod 2*^H).

(c) Jedyną liczbą pierwszą przystającą do I modliło 64 i mniejszą od y/6Ś537 jest 193. a ta liczba nic jest dzielnikiem 65537.

3. AW7J(R4, 1330) = 14.

/ os

rozważ cztery przypadki ze

4. Zap/« ( /) w.po.uci ( -/} = (j )( j)

względu na to. jaką resztę daje /? przy dzieleniu przez 8.

= -(- I)(-D= -1.

6.    (a) 14; (b) 9; (c) 9a.

7.    a³ — a (por. dowód twierdzenia 2.2.4); 6, 60, 4080, 24, 210, 336.

8.    Ponieważ q s 1 (mod />), więc istnieje pierwiastek pierwotny f stopnia

n

(a) (—- j V ( —    6. 45, 3126, 906 (w ostatnim przypadku skorzystaj

I P )}% \PJ

z równości: 1093 — (3⁷ — l)/2).

'-Wj\

(b) Niech (7 = Y l — )2^J. Wtedy najmniejszy dodatni pierwiastek kwad-

J=i W

ratowy z ^—-Jp modulo 2^P — I jest równy (?, jeśli p = 5 (mod 8); jest

BI

p z jedności w ciele F_f. Wtedy (r (por. lemat w dowodzie twierdzenia 2.2.5).

Ę¹ ma kwadrat równy

równy —G, jeśli p w 3 (mod 8); jest równy p + G, jeśli p = 7 (mod 8); jest równy p — G, jeśli /? = 1 (mod 8).

I    (a) | Cb) | (c) | (d) | (e) 1; (£) 1; gj -1.

II    (f i I ii (ł)

co jest równe 1 wtedy i tylko wtedy, gdy p = 1 (mod 3).

13. Ostatnią cyfrą dziesiętną jest 1 lub 9.

14 Każda potęga reszty kwadratowej jett reszta kwadratową. a więc żadna niereszta kwadratowa nie jest potęgą reszty kwadratowej. Zatem reszta kwadratowa nie może być generatorem.

15. (a) Ponieważ p - I jest potęgą 2, więc rząd dowolnego elementu g jest

potęgą 2. Jeśli -1 = (—) s g^lp~¹⁾¹² (mod p), to ten rząd nie może

W

być mniejszy od p - 1.

(b) Jeśli ś: > 1 i /? = 2^2k + 1, to /? = 2 (mod 5) (gdyż wykładnik tej potęgi 2

jest wielokrotnością 4). Wtedy

(c) Podobnie do (b): ponieważ wykładnik potęgi 2 nie jest podzielny przez

3, więc ta potęga dwójki przystaje do 2 łub do 4 modulo 7; stąd p = 3

16.    (a) Zachodzi równość:

(a + bi)^p*¹ = (a^p + b^pi^p)(a + ói) = (a - ói)(a + W) = a² + b². Stwierdzenie: Jeśli (a + bi)^me ¥_p, top+\\m. Aby dowieść tego stwierdzenia, przyjmijmy d = NWD(m, p +1). Rozumując tak samo jak w dowodzie twierdzenia 1.4.2, pokazujemy, że (a + bi)^d€ f_r Alt p + I jest potęgą 2, więc jeśli d < p + 1, to (a + bif^r"^m jest takim elementem F_p) którego kwadrat jest równy a² + b¹. Ale a¹ + b² jest nieresztą kwadratową (por. ćwiczenie 14). Zatem d=p +1 i p +1 \m. Teraz, gdy nasze stwierdzenie zostało udowodnione, przypuśćmy, że n = n'(p + 1) jest taką liczbą, że (a + bi)ⁿ = 1 (zauważmy, że ze stwierdzenia wynika, iż p +1 |/i). Wtedy (a² + b²)*' = 1, a więc p - l|n', gdyż a¹ + ó² jest generatorem grupy FJ.

(b) Wykaż, że 17 i 13 są generatorami grupy Ffi.

17.    W obu przypadkach otrzymujemy oszacowanie O (log³/?). Ale zauważ, że twierdzenie 2.2.2 stosuje się tylko do przypadku, gdy liczba n jest pierwsza, podczas gdy metoda z punktu (a) ma zastosowanie ogólne, dla dowolnej nieparzystej liczby dodatniej n. Zauważ też, że czas obliczeń w punkcie (a) można zmniejszyć do 0(log²p), stosując metodę wykorzystaną w ćwiczeniu 11 z podrozdziału 1.2.

18.    (a) Rozwiąż tę kongruencję metodą uzupełniania do pełnego kwadratu;

pokaż, że liczba rozwiązań jest równa liczbie rozwiązań kongruencji x² = D (mod p). Istnieje jedno rozwiązanie, gdy D = 0, nie ma rozwiązań, gdy D jest nieresztą, i są dwa rozwiązania, jeśli D jest resztą kwadratową.

(b) 0, 0, 2,1, 2; (c) 2, 2,1,0, 0.