Teoria liczb II

1. Algorytm Euklidesa Algorytm Euklidesa jest algorytmem obliczaj _{}acym NW D(a, b) dla a, b ∈ ℕ. Jest zdecydowanie szybszy niż popularnie stosowany algorytm rozkładania liczb na czynniki pierwsze i patrzenia, które s _{}a wspólne. Załóżmy bez straty ogólności, że a > b. Algorytm opiera si_{}e na spostrzeżeniu, że NW D(a, b) = NW D(b, a mod b). Zauważmy, że a mod b = a−b[\frac{a}{b}]. A zatem jeśli d | a i d | b, to d | a−b[\frac{a}{b}], czyli d | a mod b. Podobnie jeśli d | a−b[\frac{a}{b}] i d | b, to d | a. A zatem zbiór wspólnych dzielników a i b jest taki sam, co zbiór wspólnych dzielników b i a mod b, a wi_{}ec i najwi_{}eksze elementy w tych zbiorach s _{}a równe. Skoro wiemy, że NW D(a, b) = NW D(b, a mod b), to możemy kontynuować t_{}e operacj_{}e aż do otrzymania 0. Wtedy ostatnia otrzymana niezerowa liczba to właśnie NW D(a, b).

Przykład: NWD(87,72)=NWD(72,15)=NWD(15,12)=NWD(12,3)=NWD(3,0)=3

2. Dla każdych a, b ∈ ℕ istniej _{}a takie x, y ∈ ℤ, że ax + by = NW D(a, b). Dowód: można pokazać przez indukcj_{}e, że każda otrzymana w algorytmie Euklidesa liczba jest postaci ak + bl, gdzie k, l ∈ ℕ. Na pewno a = a · 1 + b · 0, b podobnie, wi_{}ec pocz _{}atek indukcji jest. Jeśli w pewnym momencie mamy c = ak_{1} + bl_{1} i d = ak_{2} + bl_{2}, to wtedy c mod d = c − d[\frac{c}{d}] = ak_{1} + bl_{1} − (ak_{2} + bl_{2}) · e, gdzie e ∈ ℤ, wi_{}ec c mod d też postaci ak + bl. Zatem na końcu dojdziemy do NW D(a, b), które też b_{}edzie tej postaci.

Zauważmy, że w tej sytuacji mamy, że gdy a ⊥ b to istniej _{}a x, y ∈ ℤ takie, że ax + by = 1.

3. NW D(a, b) · NW W (a, b) = a · b Dowód: rozpatrzmy pewn _{}a liczb_{}e pierwsz _{}a p i wykładnik, w którym wyst_{}epuje z lewej i z prawej strony. Jeśli p ∤ a i p ∤ b, to sprawa jest prosta, wykładniki to odpowiednio 0 i 0, czyli s _{}a równe. Jeśli p ∤ a, a p | b, to powiedzmy, że maksymalny wykładnik p w b to α. Wtedy w NW D(a, b) wykładnik jest 0, a w NW W (a, b) - α. A zatem również si_{}e sumuje. Gdy obie liczby s _{}a podzielne przez p w pot_{}egach odpowiednio α i β, to wykładnik przy NW D(a, b) b_{}edzie min(α, β), a przy NW W (a, b) b_{}edzie max(α, β), a wi_{}ec także po obu stronach wykładniki sumuj _{}a si_{}e do tej samej liczby. Skoro p była dowoln _{}a liczb _{}a pierwsz _{}a, to znaczy, że liczby po obu stronach s _{}a faktycznie równe.

4. Ci _{}ag Fibonacciego Ci _{}ag Fibonacciego definiuje si_{}e nast_{}epuj _{}aco: F_{0} = 0, F_{1} = 1, F_{n+2} = F_{n+1} +F_{n}. Warto znać jego pierwsze kilka wartości - 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … - pomaga to dostrzec ci _{}ag Fibonacciego w zadaniach, które w treści wcale go nie maj _{}a, a zauważenie, że tak naprawd_{}e mowa o tym ci _{}agu praktycznie rozwi _{}azuje zadanie. Ci _{}ag ten posiada sporo ciekawych własności, niektóre z nich to:

1. NW D(F_{n+1} , F_{n}) = 1

Możemy zastosować algorytm Euklidesa i dostajemy: NW D(F_{n+1} , F_{n}) = NW D(F_{n}, F_{n−1} ) = … = NW D(F_{2}, F_{1}) = NW D(F_{1}, F_{0}) = NW D(1, 0) = 1 2. F_{n}^{2} = F_{n−1} F_{n+1} + (−1)^{n+1}

Dowodzimy poprzez indukcj_{}e. Pocz _{}atek: F_{1} = F_{2} · F_{0} + 1, zgadza si_{}e. Krok: F_{n+1}^{2} = F_{n+1} (F_{n} + F_{n−1} ) = F_{n}F_{n+1} + F_{n+1} F_{n−1} = F_{n}F_{n+1} + F_{n}^{2} + (−1)^{n+1+1} = F_{n}(F_{n+1} + F_{n}) + (−1)^{n+2} = F_{n}F_{n+2} + (−1)^{n+2}

3.n | m ⇒ F_{n} | F_{m}

Rozpatrujemy reszty modulo F_{n}. F_{0} ≡ 0, F_{1} ≡ 1, F_{2} ≡ 1, F_{3} ≡ 2 …F_{n} ≡ 0, wi_{}ec jeśli F_{n+1} ≡ k, to F_{n+2} ≡ k, F_{n+3} ≡ 2k …F_{2n} ≡ F_{n} · k ≡ 0. Podobnie F_{3n} ≡ 0 itd.

Warto zauważyć, że maj _{}ac dane 2 kolejne wyrazy ci _{}agu możemy si_{}e cofać, czyli znajdować poprzednie wyrazy, tzn. 2 kolejne wyrazy tego ci _{}agu określaj _{}a cały ci _{}ag.

Konsekwencj _{}a tego jest, że reszty modulo k dla każdego k ∈ ℕ powtarzaj _{}a si_{}e, czyli jeżeli wyst _{}apił już kiedyś wyraz np. podzielny przez k, to b_{}edzie ich nieskończenie wiele.

Istnieje wzór jawny na ci _{}ag Fibonacciego, tak zwany wzór Bineta:

F_{n} = \frac{1}{\sqrt{5}}(\frac{1 + \sqrt{5}}{2} )^{n} − \frac{1}{\sqrt{5}}(\frac{1 − \sqrt{5}}{2} )^{n}

Warto wiedzieć, że taki istnieje, ale nie koniecznie trzeba go znać.

5. Liczb pierwszych jest nieskończenie wiele Dowód: Dowód przeprowadzimy nie wprost. Przypuśćmy, że jest skończenie wiele liczb pierwszych, niech b_{}ed _{}a to: p_{1}, p_{2}, …, p_{n}. Rozważmy liczb_{}e p = p_{1}p_{2}p_{3} …p_{n} + 1. Zauważmy, że p_{1} ∤ p, p_{2} ∤ p …p_{n} ∤ p, a zatem p dzieli si_{}e tylko przez 1 i przez sam _{}a siebie, wi_{}ec jest liczb _{}a pierwsz _{}a. Dodatkowo p jest wi_{}eksza od wszystkich p_{i}, wi_{}ec wcześniej rozpatrywane liczby nie były wszystkimi liczbami pierwszymi, w ten sposób doszliśmy do sprzeczności.

6. Małe twierdzenie Fermata

Niech p b_{}edzie liczb _{}a pierwsz _{}a, n ∈ ℕ, p ∤ n. Wtedy zachodzi n^{p} ≡ n mod p (inna wersja: n^{p−1} ≡ 1 mod p).

Dowód: Rozpatrzmy zbiór A = {n, 2n, 3n, …, (p−1)n} mod p. Pokażemy, że A = {1, 2, …, p− 1}. Najpierw zauważmy, że wszystkie liczby postaci in mod p s _{}a z zakresu od 1 do p − 1, bo n ⊥ p oraz i ⊥ p. Oprócz tego wszystkie te liczby s _{}a różne. Przypuśćmy, że in mod p = jn mod p. Wtedy p | in − jn, czyli p | n(i − j). Jednak p ⊥ n, wi_{}ec p | i − j. Skoro 1 i, j p − 1, to i − j = 0, czyli i = j. A zatem każde dwie liczby tej postaci s _{}a różne. Mamy wi_{}ec {n, 2n, …, (p − 1)n} mod p = {1, 2, …, p − 1} mod p. Po wymnożeniu stronami dostajemy: n^{p−1} (p − 1)! ≡ (p − 1)! mod p, jednak (p − 1)! ⊥ p, wi_{}ec n^{p−1} ≡ 1 mod p, c.n.d.

7. Tw. Eulera

Niech n ∈ ℕ, a ⊥ n, wtedy a^{φ(n)} ≡ 1 mod n.

Najpierw wyjaśnijmy, że φ(n) jest liczb _{}a liczb wzgl_{}ednie pierwszych z n mniejszych od n, φ(n) = |{1 k n : k ⊥ n}|. Zauważmy, że jeśli p jest liczb _{}a pierwsz _{}a, to φ(p) = p − 1, bo wszystkie liczby mniejsze od p s _{}a z ni _{}a wzgl_{}ednie pierwsze, a φ(p^{k}) = p^{k−1} ∗ (p − 1), bo nie s _{}a z ni _{}a wzgl_{}ednie pierwsze tylko liczby podzielne przez p, czyli co p-ta. Jednocześnie jeżeli a ⊥ b, to φ(ab) = φ(a)φ(b), w ten sposób można już obliczyć φ(n) dla każdego n ∈ ℕ. Zwróćmy uwag_{}e, że małe twierdzenie Fermata jest szczególnym przypadkiem twierdzenia Eulera, gdyż φ(p) = p − 1. Przejdźmy teraz do dowodu tw. Eulera, b_{}edzie on bardzo podobny do dowodu małego tw. Fermata.

Dowód: niech A = {ka : 1 k n, k ⊥ n} mod n. Pokażemy, że A = {k : 1 k n, k ⊥ n} mod n = B. Każda liczba ka mod n s _{}a z zakresu od 1 do n − 1 i na dodatek s _{}a wzgl_{}ednie pierwsze z n, bo k ⊥ n i a ⊥ n. Poza tym jeśli ka mod n = la mod n, to n | a(k − l), czyli n | k − l, czyli k = l. Zatem ∏ _{k∈A} ka ≡ ∏ _{k∈A} k mod n, z czego wynika, że a^{φ(n)} ∗ ∏ _{k∈A} k ≡ ∏ _{k∈A} k mod n. Jednak ponieważ ∏ _{k∈A} k ⊥ n, to a^{φ(n)} ≡ 1 mod n, c.n.d.

8. Chińskie tw. o resztach

Niech n_{1}, n_{2}, …, n_{k} ∈ ℕ, n_{i} ⊥ n_{j} dla i ≠ j, a_{1}, a_{2}, …, a_{k} ∈ ℕ. Wtedy istnieje dokładnie jedna liczba a ∈ {0, 1, …, n_{1}n_{2} …n_{k} − 1} taka, że a ≡ a_{i} mod n_{i}.

Dowód: zauważmy, najpierw, że możliwych układów reszt modulo n_{1}, n_{2}, …, n_{k} jest n_{1}n_{2} …n_{k}. Zauważmy też że dla każdej liczby z przedziału od 0 do n_{1}n_{2} …n_{k}−1 układ reszt, które daje ona modulo n_{i} jest różny. Gdyby x i y dawały ten sam układ reszt, to n_{1} | x − y, n_{2} | x − y, …, n_{k} | x − y, czyli n_{1}n_{2} …n_{k} | x − y, a to dla x i y z naszego przedziału możliwe jest tylko przy x = y. A zatem wszystkie układy reszt s _{}a przyjmowane i to każdy dokladnie raz, czyli jakkolwiek sobie nie wybierzemy ż _{}adanego układu znajdziemy dokładnie jedn _{}a liczb_{}e w naszym przedziale realizuj _{}ac _{}a te reszty, c.n.d.

9. Tw. Wilsona

n ∈ ℕ, n > 1 jest liczb _{}a pierwsz _{}a wtedy i tylko wtedy gdy (n − 1)! ≡ −1 mod n

Dowód: �⇐” Najpierw dowodzimy w lewo. Dowodzimy nie wprost. Załóżmy, że n jest złożone. A zatem n = p_{1} · p_{2}, n > p_{1}, p_{2} > 1. Wtedy p_{1} | (n − 1)!, wi_{}ec (n − 1)! nie jest wzgl_{}ednie pierwszy z n. Sprzeczność. �⇒” Teraz dowodzimy w prawo. Liczba p jest pierwsza, wi_{}ec dla każdego k istnieje odwrotność modulo p, czyli ⋀ k ⋁ l : k · l ≡ 1 mod n. Tylko dwie liczby s _{}a w parze ze sob _{}a, s _{}a to 1 oraz p − 1, gdyż aby p | x^{2} − 1 potrzeba, by p | (x + 1)(x − 1), czyli p | (x − 1) lub p | (x + 1). Liczb od 1 do p − 1 jest parzyście wiele, wi_{}ec wszystkie dobior _{}a si_{}e w pary, czyli (p − 1)! ≡ 1 mod p.