Matematyka dyskretna 1/Ćwiczenia 10: Teoria liczb

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Teoria liczb I

Ćwiczenie 1

Udowodnij, że dla , jeśli , i , to .

Wskazówka
Rozwiązanie

Ćwiczenie 2

Udowodnij, że:

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

Ćwiczenie 3

Użyj algorytmu Euklidesa dla podanych wartości do obliczenia NWD :

  • ,
  • .
Rozwiązanie

Ćwiczenie 4

Użyj rozszerzonego algorytmu Euklidesa dla podanych wartośći do wskazania współczynników takich, że NWD :

  • ,
  • .
Rozwiązanie

Ćwiczenie 5

Liczby Mersenne'a to liczby postaci . Oto lista kilku początkowych liczb Mersenne'a z pogrubionymi liczbami pierwszymi:



Pokaż, że jeśli -ta liczba Mersenne'a jest pierwsza, to jest pierwsza.

Wskazówka
Rozwiązanie

Ćwiczenie 6

Liczby Fermata to liczby postaci . Oto lista kilku początkowych liczb Fermata:



Pokaż, że

  • ,
  • , dla .
Wskazówka
Rozwiązanie

Ćwiczenie 7

Pokaż następujące własności liczb Fibonacci'ego:

  • NWD ,
  • NWD NWD , dla ,
  • NWD .
Wskazówka
Rozwiązanie