Matematyka dyskretna 1/Ćwiczenia 10: Teoria liczb
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwaniaTeoria 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