Matematyka dyskretna 1/Ćwiczenia 11: Teoria liczb II

Z Studia Informatyczne
< Matematyka dyskretna 1
Wersja z dnia 18:11, 11 cze 2020 autorstwa Luki (dyskusja | edycje) (→‎Teoria liczb II)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
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