Matematyka dyskretna 1/Ćwiczenia 11: Teoria liczb II

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Teoria liczb II

Ćwiczenie 1

Podaj zbiór rozwiązań następujących równań:

  • ,
  • ,
  • ,
  • ,
  • ,
  • .
Rozwiązanie

Ćwiczenie 2

Wyznacz najmniejsze, nieujemne rozwiązania układu równań:



Rozwiązanie

Ćwiczenie 3

Wyznacz najmniejsze, nieujemne rozwiązania układu równań:



Rozwiązanie

Ćwiczenie 4

Policz wartości funkcji Eulera:

  • ,
  • ,
  • .
Rozwiązanie

Ćwiczenie 5

Policz możliwie szybko:

  • { mod} ,
  • { mod} ,
  • { mod} .
Rozwiązanie

Ć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:

  1. funkcja Mobiusa jest multyplikatywna,
  2. jeśli funkcja jest multyplikatywna to też.
Rozwiązanie

Ć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.

Wskazówka
Rozwiązanie