5027720046

Lista 4 - Twierdzenie Eulera i pierwiastki pierwotne

1.    Oblicz tp(ri) dla: a) n = 1001; b) 111111; c) 555555; d) lOOl¹⁰⁰¹.

2.    Wyraź <p(666) za pomocą samych szóstek.

3.    Znajdź wszystkie pierwiastki pierwotne w Z\\.

4.    Czy istnieje pierwiastek pierwotny dla: a) n = 12; b) 18; c) 27?

5.    Znajdź jakikolwiek pierwiastek w Z29. Korzystając z niego znajdź wszystkie pozostałe pierwiastki pierwotne modulo 29.

6.    Ile jest pierwiastków pierwotnych w Z73?

7.    Wykaż, że jeśli r jest pierwiastkiem pierwotnym dla liczby pierwszej p, to

r^~ = —1 mod p.

8.    Jaki zachodzi związek pomiędzy <p(2n) a <p{n)l

9.    Wykaż, że równanie <p(n) = n/3 ma nieskończenie wiele rozwiązań.

10.    Czy równanie <p(n) = 14 ma rozwiązanie?

11.    Wykaż, że jedyną nieparzystą wartością funkcji Eulera jest liczba 1.

12.    Uzupełnij dowód twierdzenia Wilsona: „Niech r będzie pierwiastkiem pierwotnym modulo p. Wówczas

(p- 1)! = modp _rl+2+-+(P-l)...»

13.    Korzystając z twierdzenie Eulera wykaż, jeśli n jest liczbą nieparzystą niepodzielną przez 5, to pewna jej krotność ma zapis złożony z samych jedynek. Uwaga: Podobny wynik można uzyskać za pomocą zasady szufladkowej. Porównaj obydwa wyniki.

14.    Niech p będzie nieparzystą liczbą pierwszą. Wykaż, że suma

lⁿ + 2ⁿ + ...-t-(p- l)ⁿ

jest równa 0 bądź —1.

Wsk. Jeżeli p — 1 nie dzieli n, a r jest pierwiastkiem pierwotnym dla p, to żądana suma modulo p jest równa

1 + rⁿ + r²ⁿ + ... + r^(p-2)n.

15.    Uzasadnij, że dla liczb pierwszych p długość okresu w rozwinięciu dziesiętnym liczby 1/p jest dzielnikiem liczby p — 1.

16.    Wykaż, że jeśli F_p jest liczbą pierwszą Fermata, to 2 nie jest pierwiastkiem pierwotnym dla F_p.

17.    Znajdź kres górny i kres dolny zbioru liczb postaci <p(n)/n.