KÓŁECZKO Z TEORII LICZB (24.10.2007)

1. TEORIA

1.0. Jeśli istnieje x takie, że ax = b, to mówimy, że a|b (a dzieli b). Liczba pierwsza p to liczba naturalna wi_{}eksza od 1, której jedynymi dzielnikami jest 1 i ona

sama (x|p ⇒ (x = 1 lub x = p).

1.1. Ci _{}ag Fibonacciego (F_{n}) jest określony nast_{}epuj _{}aco: F_{1} = 1, F_{2} = 1, F_{n+2} = F_{n} + F_{n+1} dla dowolnego n ∈ ℕ.

1.2. NWD i NWW Przez NW D(a, b) oznaczamy najwi_{}ekszy wspólny dzielnik liczb całkowitych a i b (NW D(a, b)|a,

NW D(a, b)|b oraz dla każdego x całkowitego zachodzi (x|a ∧ x|b) ⇒ x|NW D(a, b)).

Przez NW W (a, b) oznaczamy najmniejsz _{}a wspóln _{}a wielokrotność liczb całowitych a i b (NW W (a, b) 0, a|NW W (a, b), b|NW W (a, b) oraz dla każego x naturalnego zachodzi (a|x ∧ b|x) ⇒ NW W (a, b)|x).

Dla dowolnych a, b ∈ ℕ istniej _{}a x, y ∈ ℤ takie, że ax + by = NW D(a, b). Jeśli NW D(a, b) = 1, to mówimy, że a⊥b (a jest wzgl_{}ednie pierwsze z b). Dla dowolnych a, b ∈ ℕ zachodzi NW D(a, b) · NW W (a, b) = ab.

1.3. Zapis a ≡ b mod n oznacza, że n|a − b.

1.4. Małe twierdzenie Fermata Niech p b_{}edzie liczb _{}a pierwsz _{}a, n ∈ ℕ, p nie dzieli n. Wtedy zachodzi: n^{p} ≡ n mod p (inna wersja: n^{p−1} ≡ 1 mod p).

1.5. Tw. Wilsona Liczba naturalna n wi_{}eksza od 2 jest liczb _{}a pierwsz _{}a wtedy i tylko wtedy gdy (n − 1)! ≡ −1 mod n.

2.ZADANKA

2.0. Udowodnić, że jest nieskończenie wiele liczb pierwszych.

2.1. Udowodnić, że:

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

• n|m ⇒ F_{n}|F_{n+1}

2.2. Wykaż, że jeśli p jest liczb _{}a pierwsz _{}a, to p|a^{p} − b^{p} ⇒ p^{2}|a^{p} − b^{p}.

2.3. Niech p b_{}edzie liczb _{}a pierwsz _{}a wi_{}eksz _{}a od 2. Niech a_{1}, a_{2}, …, a_{p−1} b_{}ed _{}a parami różnymi resztami modulo p, analogicznie b_{1}, b_{2}, …, b_{p−1} . Wykaż, że istniej _{}a różne k i l, takie że a_{k}b_{k} ≡ a_{l}b_{l} (mod p).

2.4. Liczba Grabowskiego to liczba, której zapis dziesi_{}etny składa si_{}e z samych cyfr 1. Udowodnij, że jeśli NW D(n, 10) = 1, to istnieje liczba Grabowskiego podzielna przez n.

2.5. Liczby całkowite x, y, z spełniaj _{}a warunek 7|x^{3} + y^{3} + z^{3}. Udowodnij, że 7|xyz.