KÓŁECZKO Z TEORII LICZB (13.12.06)

1. TEORIA 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} . 1.2. Dla dowolnych a, b ∈ ℕ istniej _{}a x, y ∈ ℤ takie, że ax + by = NW D(a, b). 1.3. 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.4. Tw. Wilsona: n ∈ ℕ, n 2 jest liczb _{}a pierwsz _{}a wtedy i tylko wtedy gdy (n − 1)! ≡ −1 mod n.

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

2.ZADANKA 2.1. Udowodnić, że:

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

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

2.2. Udowodnij, że jeśli 2^{n} + 1 jest liczb _{}a pierwsz _{}a, to n jest pot_{}eg _{}a dwójki. 2.3. Udowodnij, że jeśli 2^{n} − 1 jest liczb _{}a pierwsz _{}a, to n jest liczb _{}a pierwsz _{}a. 2.4. Znajdź wszystkie n, dla których n! + 3 jest kwadratem liczby naturalnej. 2.5. Udowodnij, że jeśli p|a^{p} − b^{p}, gdzie p jest liczb _{}a pierwsz _{}a, to również p^{2}|a^{p} − b^{p}. 2.6. Niech p_{n} b_{}edzie ci _{}agiem liczb pierwszych (p_{1} = 2, p_{2} = 3, p_{3} = 5, …). Udowodnić, że

(Π_{i=1}^{n} p_{i}) ± 1, dla żadnego n, nie jest kwadratem liczby naturalnej.

2.7. Udowodnić, że nie istnieje taka para liczb naturalnych n 2, k 2, takich, żeby 2^{n} −1 było k-t _{}a pot_{}eg _{}a liczby całkowitej.

2.8. Liczb_{}e nazywamy k-elfiast _{}a jeśli jest niepodzielna przez żadn _{}a liczb_{}e postaci a^{k}. Udowodnić, że dla dowolnego k, dwie kolejne liczby k-elfiaste mog _{}a być oddalone od siebie o dowolnie dużo.