Matematyka dyskretna 1/Ćwiczenia 10: Teoria liczb

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Teoria liczb I

Ćwiczenie ex tl cwiczenie - podobne podzielnosc wzglednie pierwszych liczb

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

Wskazówka
Rozwiązanie

Ćwiczenie ex tl podzielności

Udowodnij, że:

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

Ćwiczenie ex tl zapuszczenie Euklidesa

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

  • ,
  • .
Rozwiązanie

Ćwiczenie ex tl rozszerzony algorytm Euklidesa

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

  • ,
  • .
Rozwiązanie

Ćwiczenie ex tl cwiczenie - liczby Mersenne'a

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 ex tl liczby Fermata

Liczby Fermata to liczby postaci Parser nie mógł rozpoznać (nieznana funkcja „\textsl”): {\displaystyle \displaystyle \textsl{fer}_{n+1}\displaystyle =2^{2^n}+1} . Oto lista kilku początkowych liczb Fermata:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \displaystyle \begin{array} {c|c|c|c|c|c} n&0&1&2&3&4\\ \hline \mbox{\textsl{fer}_{n}<math>\displaystyle } &3&5&17&257&26987 \end{array} }

Pokaż, że

  • Parser nie mógł rozpoznać (nieznana funkcja „\textsl”): {\displaystyle \displaystyle \textsl{fer}_{n+1}\displaystyle =\prod_{i=0}^n \displaystyle \textsl{fer}_{i}\displaystyle +2} ,
  • Parser nie mógł rozpoznać (nieznana funkcja „\textsl”): {\displaystyle \displaystyle \textsl{fer}_{m}\displaystyle \perp \displaystyle \textsl{fer}_{n}} , dla .
Wskazówka
Rozwiązanie

Ćwiczenie ex tl liczby Fibonacciego

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

  • NWD ,
  • NWD NWD , dla ,
  • NWD Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (f_m,f_n)=f_{ } NWD Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (m,n)}} .
Wskazówka
Rozwiązanie