Matematyka dyskretna 1/Ćwiczenia 10: Teoria liczb: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
m
 
Linia 257: Linia 257:
 
*  NWD <math>\displaystyle  (f_n,f_{n+1})=1</math>,
 
*  NWD <math>\displaystyle  (f_n,f_{n+1})=1</math>,
 
*  NWD <math>\displaystyle  (f_m,f_n)= </math>  NWD <math>\displaystyle  (f_{n},f_{m-n})</math>, dla <math>\displaystyle m>n</math>,
 
*  NWD <math>\displaystyle  (f_m,f_n)= </math>  NWD <math>\displaystyle  (f_{n},f_{m-n})</math>, dla <math>\displaystyle m>n</math>,
*  NWD <math>\displaystyle  (f_m,f_n)= f_{NWD(f_n,f_m)}</math>.
+
*  NWD <math>\displaystyle  (f_m,f_n)= f_{NWD(n,m)}</math>.
  
 
}}
 
}}
Linia 305: Linia 305:
 
Na odwrót, z równości <math>\displaystyle (*)</math>, dowolny dzielnik <math>\displaystyle f_{m-n}</math> i <math>\displaystyle f_n</math> dzieli tez <math>\displaystyle f_m</math>,  
 
Na odwrót, z równości <math>\displaystyle (*)</math>, dowolny dzielnik <math>\displaystyle f_{m-n}</math> i <math>\displaystyle f_n</math> dzieli tez <math>\displaystyle f_m</math>,  
 
więc  NWD <math>\displaystyle  (f_m,f_n)= </math>  NWD <math>\displaystyle  (f_n,f_{m-n})</math>.
 
więc  NWD <math>\displaystyle  (f_m,f_n)= </math>  NWD <math>\displaystyle  (f_n,f_{m-n})</math>.
*  NWD <math>\displaystyle  (f_m,f_n)=f_{NWD(f_n,f_m)}</math>:
+
*  NWD <math>\displaystyle  (f_m,f_n)=f_{NWD(n,m)}</math>:
  
 
Niech <math>\displaystyle m>n</math> ma reprezentację  <math>\displaystyle m=qn+r</math>, dla pewnego <math>\displaystyle q\geqslant1</math> i <math>\displaystyle 0\leq r <n</math>.  
 
Niech <math>\displaystyle m>n</math> ma reprezentację  <math>\displaystyle m=qn+r</math>, dla pewnego <math>\displaystyle q\geqslant1</math> i <math>\displaystyle 0\leq r <n</math>.  

Aktualna wersja na dzień 16:03, 8 paź 2020

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