Ćwiczenia 3: teoria liczb - podzielność, NWD, kongruencje

Zadanie 1

Udowodnij, że iloczyn k kolejnych liczb całkowitych jest podzielny przez k!.

Zadanie 2

Udowodnij, że jeśli liczba 2ⁿ-1 jest pierwsza, to liczba n jest pierwsza.

Zadanie 3

Udowodnij, że jeśli liczba 2ⁿ+1 jest pierwsza, to n jest potęgą 2. Niech f_n = 2²ⁿ+1 oznacza n-tą liczbę Fermata. Uprość iloczyn f₀...f_n i udowodnij, że każde dwie różne liczby Fermata są względnie pierwsze.

Zadanie 4

Udowodnij, że
(a) NWD(n^a-1, n^b-1) = n^NWD(a,b)-1;
(b) NWD(F_a, F_b) = F_NWD(a,b), gdzie F_n to n-ta liczba Fibonacciego.

Zadanie 5

Ile rozwiązań ma kongruencja ax ≡ b (mod n) w zbiorze {0,...,n-1}. Jak je efektywnie znajdować?

Zadanie 6

Udowodnij twierdzenie Wilsona: liczba n jest pierwsza <=> (n-1)! ≡ -1 (mod n).