Materiały dydaktyczne – Wybrane zagadnienia Matematyki Dyskretnej (Zestaw 4) Wybrane zagadnienia Matematyki Dyskretnej Zestaw 4

1. Korzystając z sita Eratostenesa wskaż kilka 10-cyfrowych liczb pierwszych.-

2. Korzystając z algorytmu Fermata rozłóż na czynniki liczbę 11111 (bez użycia komputera).

3. Korzystając z Małego Twierdzenia Fermata udowodnij, że 232 + 1 nie jest liczbą pierwszą (oblicz 3232 (mod 232 + 1)).

4. Oblicz wartości π(500), π(5000), π(50000).

5. Liczba złożoną n nazywamy liczbą Carmichaela jeśli dla dowolnego b ∈

∗

Zn zachodzi równość

bn−1 ≡ 1

(mod n).

Udowodnij, że następujące liczby są liczbami Carmichaela: 1105, 1729, 2465, 2821, 6601, 29341, 172081, 278545. Rozłóż je na czynniki.

1