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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m Zastępowanie tekstu – „<math> ” na „<math>”
m Zastępowanie tekstu – „.↵</math>” na „</math>”
Linia 240: Linia 240:




<center> <math>\mathit{fer}_{n}\mod\mathit{fer}_{m}=2.
<center> <math>\mathit{fer}_{n}\mod\mathit{fer}_{m}=2</math></center>
</math></center>




Linia 247: Linia 246:




<center>  NWD <math>( \mathit{fer}_{n}  , \mathit{fer}_{m}  )=</math>  NWD <math>( \mathit{fer}_{m}  ,2)=1.
<center>  NWD <math>( \mathit{fer}_{n}  , \mathit{fer}_{m}  )=</math>  NWD <math>( \mathit{fer}_{m}  ,2)=1</math></center>
</math></center>




Linia 279: Linia 277:




<center><math>f_{n+1}=f_{n-1}+f_n.
<center><math>f_{n+1}=f_{n-1}+f_n</math></center>
</math></center>





Wersja z 21:38, 11 wrz 2023

Teoria liczb I

Ćwiczenie 1

Udowodnij, że dla a,b,n, jeśli a|n, b|n i ab, to ab|n.

Wskazówka
Rozwiązanie

Ćwiczenie 2

Udowodnij, że:

  • 2|n2n,
  • 6|n3n,
  • 30|n5n,
  • 10|22n6, dla n2.
Rozwiązanie

Ćwiczenie 3

Użyj algorytmu Euklidesa dla podanych wartości a,b do obliczenia NWD (a,b):

  • 101,1001,
  • 55,89.
Rozwiązanie

Ćwiczenie 4

Użyj rozszerzonego algorytmu Euklidesa dla podanych wartośći a,b do wskazania współczynników x,y takich, że NWD (a,b)=xa+yb:

  • 21,111,
  • 25,115.
Rozwiązanie

Ćwiczenie 5

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


n012345678910111213mn01𝟑𝟕15𝟑𝟏63𝟏𝟐𝟕255511102320474095𝟖𝟏𝟗𝟏


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

Wskazówka
Rozwiązanie

Ćwiczenie 6

Liczby Fermata to liczby postaci fern+1=22n+1. Oto lista kilku początkowych liczb Fermata:


n01234fern351725726987


Pokaż, że

  • fern+1=i=0nferi+2,
  • fermfern , dla mn.
Wskazówka
Rozwiązanie

Ćwiczenie 7

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

  • NWD (fn,fn+1)=1,
  • NWD (fm,fn)= NWD (fn,fmn), dla m>n,
  • NWD (fm,fn)=fNWD(n,m).
Wskazówka
Rozwiązanie