5027720045

Lista 3 -Kongruencje, MTF i twierdzenie Wilsona

1. Oblicz: a) 10"¹ mod 111; b) 51^-1 mod 169; c) lOOO"¹ mod 1003.

2. Oblicz odwrotność 11 mod 257 na dwa sposoby:

a) za pomocą algorytmu Euklidesa; b) za pomocą MTF.

3. Rozwiąż kongruencję 119rr + 31 = 191a; mod 625.

4. Wykaż, że

2³⁴⁰ = 1 mod 341, chociaż 341 jest liczbą złożoną.

5. Korzystając z twierdzenia Wilsona znajdź resztę z dzilenia przez 101 liczby: a) 100!; b) 99!.

6. Udowodnij MTF dla dodatnich a korzystając z indukcji matematycznej i wzoru Newtona.

7. Udowodnij, że dla liczb pierwszych p zachodzi (p — 2)! = 1 mod p.

8. Podaj piątą kartę w sztuczce z kartami, gdy pierwszymi czterema były kolejno:

a) as pik, król pik, dama pik, walet pik;

b) dama pik, trójka pik, siódemka pik i as pik.

9. Czy w sztuczce z kartami każda czwórka kart da się odkodować?

10. Jakie wartości przyjmuje funkcja /(n) = (n — 1)! mod n?

11. Wykaż, że la nieparzystej liczby pierwszej p zachodzą kongruencje:

a) l² • 3² • 5² •... • (p - 2)² = (—1)^“ mod p;

b) 2² ■ 4²]6² ■ ... ■ (p - l)² = (-1)“ mod p.

12. Wykaż, że liczba 561 jest liczbą Carmichaela, tzn. dla dowolnego a względnie pierwszego z 561 zachodzi kongruencja

_a*(56l) = 1 mod 561.

Wykaż, iż także liczba 41041 jest liczbą Carmichaela.

13. Wykaż, że potęga liczby pierwszej nie jest liczbą Carmichaela.

14. Wykaż, że żadna liczba parzysta nie jest liczbą Carmichaela.

15. Wykaż, że każda liczba Carmichaela ma przynajmniej trzy dzielniki pierwsze,