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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
m
 
(Nie pokazano 15 wersji utworzonych przez 4 użytkowników)
Linia 1: Linia 1:
 
==Teoria liczb I==
 
==Teoria liczb I==
  
{{cwiczenie|ex tl cwiczenie - podobne podzielnosc wzglednie pierwszych liczb||
+
{{cwiczenie|1|cw 1|
 
 
 
Udowodnij, że dla  <math>\displaystyle a,b,n\in\mathbb{N}</math>, jeśli <math>\displaystyle a|n</math>, <math>\displaystyle b|n</math> i <math>\displaystyle a\perp b</math>, to <math>\displaystyle ab|n</math>.  
 
Udowodnij, że dla  <math>\displaystyle a,b,n\in\mathbb{N}</math>, jeśli <math>\displaystyle a|n</math>, <math>\displaystyle b|n</math> i <math>\displaystyle a\perp b</math>, to <math>\displaystyle ab|n</math>.  
  
Linia 19: Linia 18:
 
o jednoznaczności rozkładu na liczby pierwsze,  
 
o jednoznaczności rozkładu na liczby pierwsze,  
 
iloczyn   
 
iloczyn   
 +
  
 
<center><math>\displaystyle p_1^{\alpha_1}\ldots p_k^{\alpha_k}q_1^{\beta_1}\ldots q_l^{\beta_l}=ab
 
<center><math>\displaystyle p_1^{\alpha_1}\ldots p_k^{\alpha_k}q_1^{\beta_1}\ldots q_l^{\beta_l}=ab
 
</math></center>
 
</math></center>
 +
  
 
musi wystąpić w rozkładzie liczby <math>\displaystyle n</math>.
 
musi wystąpić w rozkładzie liczby <math>\displaystyle n</math>.
 
</div></div>
 
</div></div>
  
{{cwiczenie|ex tl podzielności||
+
{{cwiczenie|2|cw 2|
 
 
 
Udowodnij, że:
 
Udowodnij, że:
 
* <math>\displaystyle 2|n^2-n</math>,
 
* <math>\displaystyle 2|n^2-n</math>,
Linia 49: Linia 49:
 
* <math>\displaystyle 30|n^5-n</math>:
 
* <math>\displaystyle 30|n^5-n</math>:
  
Dowód indukcyjny.  
+
Dowód indukcyjny. Dla <math>\displaystyle n=0</math> mamy <math>\displaystyle 30|0</math>. Ponadto
Dla <math>\displaystyle n=0</math> mamy <math>\displaystyle 30|0</math>.  
+
 
Ponadto
 
  
<center><math>\displaystyle \aligned (n+1)^5-(n+1)&=(n^5+5n^4+10n^3+10n^2+5n+1)-(n+1)\\
+
<center><math>\displaystyle \begin{align} (n+1)^5-(n+1)&=(n^5+5n^4+10n^3+10n^2+5n+1)-(n+1)\\
 
&=(n^5-n)+(5n^4+10n^3+10n^2+5n)\\
 
&=(n^5-n)+(5n^4+10n^3+10n^2+5n)\\
 
&=(n^5-n)+5n(n+1)(n^2+n+1).
 
&=(n^5-n)+5n(n+1)(n^2+n+1).
\endaligned</math></center>
+
\end{align}</math></center>
 +
 
  
 
Pierwszy składnik jest podzielny przez <math>\displaystyle 30</math> na mocy założenia indukcyjnego.  
 
Pierwszy składnik jest podzielny przez <math>\displaystyle 30</math> na mocy założenia indukcyjnego.  
Linia 68: Linia 68:
 
* <math>\displaystyle 10|2^{2^n}-6</math>, dla <math>\displaystyle n\geqslant2</math>:
 
* <math>\displaystyle 10|2^{2^n}-6</math>, dla <math>\displaystyle n\geqslant2</math>:
  
Dowód indukcyjny.  
+
Dowód indukcyjny. Dla <math>\displaystyle n=2</math> mamy <math>\displaystyle 2^{2^2}-6=16-6=10</math>, czyli <math>\displaystyle 10|2^{2^2}</math>.  
Dla <math>\displaystyle n=2</math> mamy <math>\displaystyle 2^{2^2}-6=16-6=10</math>, czyli <math>\displaystyle 10|2^{2^2}</math>.  
 
 
Ponadto, gdy <math>\displaystyle 2^{2^n}-6=10k</math>, to:
 
Ponadto, gdy <math>\displaystyle 2^{2^n}-6=10k</math>, to:
  
<center><math>\displaystyle 2^{2^{n+1}}-6=2^{2^n\cdot2}-6=(10k+6)^2-6=(100k^2+120k+36)-6=100k^2+120k+30,
+
 
 +
<center><math>\displaystyle 2^{2^{n+1}}-6=2^{2^n\cdot2}-6=(10k+6)^2-6=(100k^2+120k+36)-6</math><math>=100k^2+120k+30,
 
</math></center>
 
</math></center>
 +
  
 
co jest oczywiście podzielne przez <math>\displaystyle 10</math>.  
 
co jest oczywiście podzielne przez <math>\displaystyle 10</math>.  
Linia 79: Linia 80:
 
</div></div>
 
</div></div>
  
{{cwiczenie|ex tl zapuszczenie Euklidesa||
+
{{cwiczenie|3|cw 3|
 
+
Użyj algorytmu Euklidesa dla podanych wartości <math>\displaystyle a,b</math> do obliczenia NWD <math>\displaystyle  (a,b)</math>:
Użyj algorytmu Euklidesa dla podanych wartości <math>\displaystyle a,b</math> do obliczenia   NWD <math>\displaystyle  (a,b)</math>:
 
 
* <math>\displaystyle 101,1001</math>,
 
* <math>\displaystyle 101,1001</math>,
 
* <math>\displaystyle 55,89</math>.
 
* <math>\displaystyle 55,89</math>.
Linia 99: Linia 99:
 
\end{array}  
 
\end{array}  
 
</math></center>
 
</math></center>
 +
 
* <math>\displaystyle 55,89</math>:
 
* <math>\displaystyle 55,89</math>:
  
Linia 114: Linia 115:
 
\end{array}  
 
\end{array}  
 
</math></center>
 
</math></center>
 +
  
 
</div></div>
 
</div></div>
  
{{cwiczenie|ex tl rozszerzony algorytm Euklidesa||
+
{{cwiczenie|4|cw 4|
 
+
Użyj rozszerzonego algorytmu Euklidesa dla podanych wartośći <math>\displaystyle a,b</math> do wskazania współczynników <math>\displaystyle x,y</math> takich, że NWD <math>\displaystyle  (a,b)=xa+yb</math>:
Użyj rozszerzonego algorytmu Euklidesa dla podanych wartośći <math>\displaystyle a,b</math> do wskazania współczynników <math>\displaystyle x,y</math> takich, że   NWD <math>\displaystyle  (a,b)=xa+yb</math>:
 
 
* <math>\displaystyle 21,111</math>,
 
* <math>\displaystyle 21,111</math>,
 
* <math>\displaystyle 25,115</math>.
 
* <math>\displaystyle 25,115</math>.
  
 
}}
 
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> 
 
</div></div>
 
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
Linia 139: Linia 137:
 
</math></center>
 
</math></center>
  
<center><math>\displaystyle \aligned 3&={\bf21}-3\cdot{\bf6}=21-3\cdot(111-5\cdot21)\\
+
 
&=-3\cdot{\bf111}+14\cdot{\bf21}
+
<center><math>\displaystyle \begin{align} 3&={\bf21}-3\cdot{\bf6}=21-3\cdot(111-5\cdot21)\\
\endaligned</math></center>
+
&=-3\cdot{\bf111}+16\cdot{\bf21}
 +
\end{align}</math></center>
 +
 
 
* <math>\displaystyle 25,115</math>:
 
* <math>\displaystyle 25,115</math>:
  
Linia 153: Linia 153:
 
</math></center>
 
</math></center>
  
<center><math>\displaystyle \aligned 5&={\bf15}-{\bf10}=15-(25-15)\\
+
 
 +
<center><math>\displaystyle \begin{align} 5&={\bf15}-{\bf10}=15-(25-15)\\
 
&=-{\bf25}+2\cdot{\bf15}=-25+2\cdot(115-4\cdot25)\\
 
&=-{\bf25}+2\cdot{\bf15}=-25+2\cdot(115-4\cdot25)\\
 
&=2\cdot{\bf115}-9\cdot{\bf25}
 
&=2\cdot{\bf115}-9\cdot{\bf25}
\endaligned</math></center>
+
\end{align}</math></center>
 +
 
  
 
</div></div>
 
</div></div>
  
{{cwiczenie|ex tl cwiczenie - liczby Mersenne'a||
+
{{cwiczenie|5|cw 5|
 
 
 
Liczby Mersenne'a to liczby postaci <math>\displaystyle m_n=2^n-1</math>.  
 
Liczby Mersenne'a to liczby postaci <math>\displaystyle m_n=2^n-1</math>.  
 
Oto lista kilku początkowych liczb Mersenne'a z pogrubionymi liczbami pierwszymi:
 
Oto lista kilku początkowych liczb Mersenne'a z pogrubionymi liczbami pierwszymi:
 +
  
 
<center><math>\displaystyle \begin{array} {|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
 
<center><math>\displaystyle \begin{array} {|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
Linia 173: Linia 175:
 
\end{array}  
 
\end{array}  
 
</math></center>
 
</math></center>
 +
  
 
Pokaż, że jeśli <math>\displaystyle n</math>-ta liczba Mersenne'a jest pierwsza, to <math>\displaystyle n</math> jest pierwsza.  
 
Pokaż, że jeśli <math>\displaystyle n</math>-ta liczba Mersenne'a jest pierwsza, to <math>\displaystyle n</math> jest pierwsza.  
Linia 184: Linia 187:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
 
Załóżmy, że <math>\displaystyle n</math> jest złożona, czyli <math>\displaystyle n=ab</math> dla pewnych <math>\displaystyle b\geq a>1</math>. Wtedy
 
Załóżmy, że <math>\displaystyle n</math> jest złożona, czyli <math>\displaystyle n=ab</math> dla pewnych <math>\displaystyle b\geq a>1</math>. Wtedy
 +
  
 
<center><math>\displaystyle 2^n-1=2^{ab}-1=(2^a-1)(2^{a(b-1)}+2^{a(b-2)}+\ldots+2^a+1)
 
<center><math>\displaystyle 2^n-1=2^{ab}-1=(2^a-1)(2^{a(b-1)}+2^{a(b-2)}+\ldots+2^a+1)
 
</math></center>
 
</math></center>
 +
  
 
Oba czynniki po prawej stronie są większe od <math>\displaystyle 1</math>, zatem <math>\displaystyle 2^n-1</math> jest złożona.
 
Oba czynniki po prawej stronie są większe od <math>\displaystyle 1</math>, zatem <math>\displaystyle 2^n-1</math> jest złożona.
 
</div></div>
 
</div></div>
  
{{cwiczenie|ex tl liczby Fermata||
+
{{cwiczenie|6|cw 6|
 +
Liczby Fermata to liczby postaci  <math>\displaystyle \mathit{fer}_{n+1}\displaystyle  =2^{2^n}+1</math>.
 +
Oto lista kilku początkowych liczb Fermata:
  
Liczby Fermata to liczby postaci  <math>\displaystyle \textsl{fer}_{n+1}\displaystyle  =2^{2^n}+1</math>.
 
Oto lista kilku początkowych liczb Fermata:
 
  
 
<center><math>\displaystyle \begin{array} {c|c|c|c|c|c}
 
<center><math>\displaystyle \begin{array} {c|c|c|c|c|c}
 
n&0&1&2&3&4\\
 
n&0&1&2&3&4\\
 
\hline
 
\hline
\mbox{</math>''fer''_{n}<math>\displaystyle } &3&5&17&257&26987
+
\mathit{fer}_{n}&3&5&17&257&26987
 
\end{array}  
 
\end{array}  
 
</math></center>
 
</math></center>
 +
  
 
Pokaż, że
 
Pokaż, że
*  <math>\displaystyle \textsl{fer}_{n+1}\displaystyle  =\prod_{i=0}^n \displaystyle \textsl{fer}_{i}\displaystyle  +2</math>,
+
*  <math>\displaystyle \mathit{fer}_{n+1}\displaystyle  =\prod_{i=0}^n \displaystyle \mathit{fer}_{i}\displaystyle  +2</math>,
*  <math>\displaystyle \textsl{fer}_{m}\displaystyle  \perp  \displaystyle \textsl{fer}_{n}</math> , dla <math>\displaystyle m\neq n</math>.
+
*  <math>\displaystyle \mathit{fer}_{m}\displaystyle  \perp  \displaystyle \mathit{fer}_{n}</math> , dla <math>\displaystyle m\neq n</math>.
  
 
}}
 
}}
Linia 216: Linia 222:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
 
Pierwszy wzór łatwo zweryfikować indukcyjnie.
 
Pierwszy wzór łatwo zweryfikować indukcyjnie.
Rzeczywiście  <math>\displaystyle \textsl{fer}_{1}\displaystyle  = 5 = 3+2 =  \displaystyle \textsl{fer}_{0}\displaystyle  +2</math>.  
+
Rzeczywiście  <math>\displaystyle \mathit{fer}_{1}\displaystyle  = 5 = 3+2 =  \displaystyle \mathit{fer}_{0}\displaystyle  +2</math>.  
 
Ponadto:
 
Ponadto:
  
<center><math>\displaystyle \aligned   \displaystyle \textsl{fer}_{n+1}\displaystyle   
+
 
 +
<center><math>\displaystyle \begin{align}   \displaystyle \mathit{fer}_{n+1}\displaystyle   
 
&=2^{2^{n+1}}+1
 
&=2^{2^{n+1}}+1
 
=2^{2^n\cdot2}+1
 
=2^{2^n\cdot2}+1
=  \displaystyle \textsl{fer}_{n}\displaystyle  ^2-2  \displaystyle \textsl{fer}_{n}\displaystyle  +2\\
+
=  \displaystyle \mathit{fer}_{n}\displaystyle  ^2-2  \displaystyle \mathit{fer}_{n}\displaystyle  +2\\
&=  \displaystyle \textsl{fer}_{n}\displaystyle  (  \displaystyle \textsl{fer}_{n}\displaystyle  -2)+2
+
&=  \displaystyle \mathit{fer}_{n}\displaystyle  (  \displaystyle \mathit{fer}_{n}\displaystyle  -2)+2
=  \displaystyle \textsl{fer}_{n}\displaystyle  \cdot\prod_{i=0}^{n-1}  \displaystyle \textsl{fer}_{i}\displaystyle  +2
+
=  \displaystyle \mathit{fer}_{n}\displaystyle  \cdot\prod_{i=0}^{n-1}  \displaystyle \mathit{fer}_{i}\displaystyle  +2
=\prod_{i=0}^n  \displaystyle \textsl{fer}_{i}\displaystyle  +2.
+
=\prod_{i=0}^n  \displaystyle \mathit{fer}_{i}\displaystyle  +2.
\endaligned</math></center>
+
\end{align}</math></center>
 +
 
  
 
Dla dowodu drugiego zauważmy, że przy  <math>\displaystyle m<n</math> punkt pierwszy daje  
 
Dla dowodu drugiego zauważmy, że przy  <math>\displaystyle m<n</math> punkt pierwszy daje  
<math>\displaystyle \textsl{fer}_{m}\displaystyle  |  \displaystyle \textsl{fer}_{n}\displaystyle  -2</math>, czyli
+
<math>\displaystyle \mathit{fer}_{m}\displaystyle  |  \displaystyle \mathit{fer}_{n}\displaystyle  -2</math>, czyli
 +
 
  
<center> <math>\displaystyle \textsl{fer}_{n}</math>  { mod}  <math>\displaystyle \textsl{fer}_{m}\displaystyle  =2.
+
<center> <math>\displaystyle \mathit{fer}_{n}\mod\mathit{fer}_{m}=2.
 
</math></center>
 
</math></center>
 +
  
 
Z drugiej strony, wprost z definicji, każda liczba Fermata jest nieparzysta, zatem
 
Z drugiej strony, wprost z definicji, każda liczba Fermata jest nieparzysta, zatem
  
<center>  NWD <math>\displaystyle  (  \displaystyle \textsl{fer}_{n}\displaystyle  ,  \displaystyle \textsl{fer}_{m}\displaystyle  )= </math>  NWD <math>\displaystyle  (  \displaystyle \textsl{fer}_{m}\displaystyle  ,2)=1.
+
 
 +
<center>  NWD <math>\displaystyle  (  \displaystyle \mathit{fer}_{n}\displaystyle  ,  \displaystyle \mathit{fer}_{m}\displaystyle  )= </math>  NWD <math>\displaystyle  (  \displaystyle \mathit{fer}_{m}\displaystyle  ,2)=1.
 
</math></center>
 
</math></center>
 +
  
 
</div></div>
 
</div></div>
  
{{cwiczenie|ex tl liczby Fibonacciego||
+
{{cwiczenie|7|cw 7|
 
 
 
Pokaż następujące własności liczb Fibonacci'ego:
 
Pokaż następujące własności liczb Fibonacci'ego:
 
*  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_{ </math>  NWD <math>\displaystyle  (m,n)}</math>.
+
*  NWD <math>\displaystyle  (f_m,f_n)= f_{NWD(n,m)}</math>.
  
 
}}
 
}}
Linia 253: Linia 264:
 
Pierwszy punkt udowodnij indukcyjnie.<br>
 
Pierwszy punkt udowodnij indukcyjnie.<br>
 
W drugim wykorzystaj zależność <math>\displaystyle f_{a+b}=f_a f_{b+1}+f_{a-1} f_b</math>.<br>
 
W drugim wykorzystaj zależność <math>\displaystyle f_{a+b}=f_a f_{b+1}+f_{a-1} f_b</math>.<br>
Dla dowodu trzeciego pokaż, że  NWD <math>\displaystyle  (f_m,f_n)= </math>  NWD <math>\displaystyle  (f_n,f_{m </math>  { mod}  <math>\displaystyle  n})</math>, dla <math>\displaystyle m>n</math>.  
+
Dla dowodu trzeciego pokaż, że  NWD <math>\displaystyle  (f_m,f_n)= </math>  NWD <math>\displaystyle  (f_n,f_{m \mod n}) \text{ dla } m>n</math>.  
 
</div></div>
 
</div></div>
  
Linia 264: Linia 275:
 
że dla mniejszych wartości jest prawdziwa.  
 
że dla mniejszych wartości jest prawdziwa.  
  
Niech teraz <math>\displaystyle d\geqslant1</math> będzie wspólnym dzielnikiem <math>\displaystyle f_n</math> oraz <math>\displaystyle f_{n+1}</math>.  
+
Niech teraz <math>\displaystyle d\geqslant1</math> będzie wspólnym dzielnikiem <math>\displaystyle f_n</math> oraz <math>\displaystyle f_{n+1}</math>.
Ponieważ  
+
Ponieważ
 +
 
  
 
<center><math>\displaystyle f_{n+1}=f_{n-1}+f_n.
 
<center><math>\displaystyle f_{n+1}=f_{n-1}+f_n.
 
</math></center>
 
</math></center>
 +
  
 
i <math>\displaystyle d</math> dzieli lewą stronę równości  
 
i <math>\displaystyle d</math> dzieli lewą stronę równości  
Linia 278: Linia 291:
 
Niech <math>\displaystyle m>n</math>.  
 
Niech <math>\displaystyle m>n</math>.  
 
Z zależności przytoczonej we wskazówce mamy
 
Z zależności przytoczonej we wskazówce mamy
 +
  
 
<center><math>\displaystyle f_m=f_{m-n}f_{n+1}+f_{m-n-1}f_n.\qquad(*)
 
<center><math>\displaystyle f_m=f_{m-n}f_{n+1}+f_{m-n-1}f_n.\qquad(*)
 
</math></center>
 
</math></center>
 +
  
 
Niech <math>\displaystyle d>1</math> dzieli tak <math>\displaystyle f_m</math> jak i <math>\displaystyle f_n</math>.  
 
Niech <math>\displaystyle d>1</math> dzieli tak <math>\displaystyle f_m</math> jak i <math>\displaystyle f_n</math>.  
Linia 290: 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_{ </math>  NWD <math>\displaystyle  (m,n)}</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>.  
Linia 296: Linia 311:
 
z drugiego punktu tego zadania dostajemy:
 
z drugiego punktu tego zadania dostajemy:
  
<center><math>\displaystyle \aligned  </math> NWD <math>\displaystyle  (f_m,f_n)&= </math> NWD <math>\displaystyle  (f_{m-n},f_n)= </math>  NWD <math>\displaystyle  (f_{m-2n},f_n)=\ldots\\
+
 
&= </math>  NWD <math>\displaystyle  (f_{m-qn},f_n)= </math>  NWD <math>\displaystyle  (f_n,f_r).
+
<center><math>\displaystyle \begin{align} \text{ NWD } \displaystyle  (f_m,f_n)&= \mbox{ NWD } \displaystyle  (f_{m-n},f_n)= \mbox{ NWD } \displaystyle  (f_{m-2n},f_n)=\ldots\\
\endaligned</math></center>
+
&= \mbox{ NWD } \displaystyle  (f_{m-qn},f_n)= \mbox{ NWD } \displaystyle  (f_n,f_r).
 +
\end{align}</math></center>
 +
 
  
 
Oznacza to, że indeksy liczb Fibonacciego możemy przekształcać  tak,   
 
Oznacza to, że indeksy liczb Fibonacciego możemy przekształcać  tak,   

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