Matematyka dyskretna 1/Ćwiczenia 11: Teoria liczb II
Teoria liczb II
Ćwiczenie 1
Podaj zbiór rozwiązań następujących równań:
- ,
- ,
- ,
- ,
- ,
- .
Ćwiczenie 2
Wyznacz najmniejsze, nieujemne rozwiązania układu równań:
Ćwiczenie 3
Wyznacz najmniejsze, nieujemne rozwiązania układu równań:
Ćwiczenie 4
Policz wartości funkcji Eulera:
- ,
- ,
- .
Ćwiczenie 5
Policz możliwie szybko:
- { mod} ,
- { mod} ,
- { mod} .
Ćwiczenie 6
Funkcja
liczbowa określona na zbiorze jest multyplikatywna, jeśli dla dowolnych względnie pierwszych zachodzi
Widzieliśmy, że -Eulera jest multyplikatywna. Pokaż, że:
- funkcja Mobiusa jest multyplikatywna,
- jeśli funkcja jest multyplikatywna to też.
Ćwiczenie 7
Udowodnij, że liczba naturalna
jest pierwsza wtedy i tylko wtedy, gdy .Komentarz: Fakt ten znany jest jako Twierdzenie Wilsona. Pierwszy te prawidłowość zauważył John Wilson, student Edwarda Waringa. Żaden z nich nie był w stanie tego udowodnić. Pierwszy dowód przedstawił Lagrange w 1773 roku. Twierdzenie to daje potencjalną możliwość sprawdzenia czy liczba naturalna jest pierwsza. Nie znamy jednak efektywnych algorytmów obliczania silni, nawet w arytmetyce modularnej.