Ciało ℤ_{p} - skrypt

DEF. Ciało - trójka (A, +, ·) w którym dwa działania wykonywane s _{}a na elementach ze zbioru A, posiadaj _{}a elementy neutralne, każdy element ma element odwrotny dodawania i każdy oprócz elementu neutralnego dodawania ma element odwrotny mnożenia. W ciele ℤ_{p} ponadto A = {0, 1, …, p − 1} i dodawanie i mnożenie odbywa si_{}e modulo p, wi_{}ec na przykład jest przemienne.

WŁ1. Dla każdego t ∈ A oraz k ∈ A, gdzie k ≠ 0 istnieje takie s ∈ A, że s · t = k. (w szczególnym przypadku dla k = 1 jest to istnienie odwrotności)

DEF. Reszt _{}a kwadratow _{}a modulo p nazywamy takie a ∈ A, że istnieje t ∈ A, że t^{2} = a.

1. Pokazać, że reszt kwadratowych jest \frac{p+1}{2} .

2. Pokazać, że 1 · 2 · . . . · (p − 1) ≡ −1(modp)

WŁ2. Wielomiany w ciele ℤ_{p} działaj _{}a tak samo jak w liczbach rzeczywistych - jeśli wielomian dla pewnego k daje zero, to mog_{}e go podzielić przez (x − k). (tw. Bezout)

1. Jeśli mamy wielomian kwadratowy W (x) o współczynnikach całkowitych i p > 3 pierwsze oraz p|W (0), W (1), W (2), to W (x) jest tożsamośiowo podzielny przez p.

WŁ3. Zachodzi małe tw. Fermata - a^{p−1} ≡ 1(modp).

1. Ile może być wówczas a^{\frac{p−1}{2}} ?

2. Pokazać, że jeśli σ(a) - najmniejsza liczba dodatnia, że a^{σ(a)} ≡ 1(modp), to σ(a)|p − 1. (σ(a) - rz _{}ad a modulo p)

DEF. (\frac{a}{p}) - symbol Legendre’a, daje 1, gdy jest reszt _{}a kwadratow _{}a i (−1) gdy nie jest.

1. Pokazać, że (\frac{a}{p}) = a^{\frac{p−1}{2}} .

2. Pokazać, że ∑ _{i=1}^{p−1} (\frac{i}{p}) = 0.

WŁ4. Własności symbolu Legendre’a:

• (\frac{a}{p})(\frac{b}{p}) = (\frac{ab}{p})

• a, b - pierwsze: (\frac{a}{b})(\frac{b}{a}) = (−1)^{\frac{a−1}{2} · \frac{b−1}{2}} (prawo wzajemności)

• (\frac{2}{p}) = (−1)^{\frac{p^{2}−1}{8}}

1. Pokazać, że jeśli liczba pierwsza p jest postaci 3k + 2, to wszystkie reszty sześcienne s _{}a różne.

WŁ5. Twierdzenie o generatorze - istnieje takie g ∈ A, że dla niego σ(g) = p − 1, czyli przemnażaj _{}ac g przez siebie uzyskujemy wszystkie rórne liczby aż po p − 1 krokach uzyskamy 1. Zatem A mog_{}e przedstawić jako {0} ∪ {g^{0}, g^{1}, …, g^{p−2} }.

0. Pokazać, że generator nie jest reszt _{}a kwadratow _{}a.

1. Pokazać, że dla dowolnego 1 k p − 2 zachodzi:

p|1^{k} + 2^{k} + … + (p − 1)^{k}

.

2. Pokazać, że 1 · 2 · . . . · (p − 1) ≡ −1(modp)

ZADANIA NA KONIEC

1. Pokazać, że dla każdego n postaci 4m^{2} − 5 istniej _{}a takie a, b ∈ ℤ^{+} , że ci _{}ag f_{i} określony nast_{}epuj _{}aco f_{0} = a, f_{1} = b, f_{i+2} = f_{i+1} + f_{i}, nie ma wyrazów podzielnych przez n.

2. Niech q|\frac{p^{p}−1}{p−1} , gdzie p, q s _{}a liczbami pierwszymi nieparzystymi. Pokazać, że p|q − 1.

3. k-t _{}a liczb _{}a Fermata nazywamy liczb_{}e postaci F_{k} = 2^{2^{k}} + 1. Pokazać, że jeśli dla n > 0 zachodzi F_{n}|3^{\frac{Fn −1}{2}} + 1, to F_{n} jest pierwsze.