Tekst źródłowy strony Matematyka dyskretna 1/Ćwiczenia 10: Teoria liczb

==Teoria liczb I==

{{cwiczenie|1|cw 1|
Udowodnij, że dla  <math>a,b,n\in\mathbb{N}</math>, jeśli <math>a|n</math>, <math>b|n</math> i <math>a\perp b</math>, to <math>ab|n</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">  
Rozłóż <math>a</math> i <math>b</math> na czynniki pierwsze.
</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">  
Rozważmy rozkłady  <math>a=p_1^{\alpha_1}\ldots p_k^{\alpha_k}</math> 
i <math>b=q_1^{\beta_1}\ldots q_l^{\beta_l}</math>. 
Ponieważ <math>a\perp b</math>, 
to żadna liczba pierwsza nie pojawia się jednocześnie w rozkładzie <math>a</math> i <math>b</math>. 
Zatem z Fundamentalnego Twierdzenia Arytmetyki 
o jednoznaczności rozkładu na liczby pierwsze, 
iloczyn  


<center><math>p_1^{\alpha_1}\ldots p_k^{\alpha_k}q_1^{\beta_1}\ldots q_l^{\beta_l}=ab
</math></center>


musi wystąpić w rozkładzie liczby <math>n</math>.
</div></div>

{{cwiczenie|2|cw 2|
Udowodnij, że:
* <math>2|n^2-n</math>,
* <math>6|n^3-n</math>,
* <math>30|n^5-n</math>,
* <math>10|2^{2^n}-6</math>, dla <math>n\geqslant2</math>.

}}

<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">  
* <math>2|n^2-n</math>:

Mamy <math>n^2-n=n(n-1)</math> i jedna spośród dwu kolejnych liczb naturalnych <math>n-1,n</math> jest parzysta,  
zatem i ich iloczyn jest parzysty.
* <math>6|n^3-n</math>:

Mamy <math>n^3-n=n(n^2-1)=n(n-1)(n+1)</math> i przynajmniej jedna 
z trzech kolejnych liczb <math>n-1,n,n+1</math> jest podzielna przez <math>2</math> 
i przynajmniej jedna jest podzielna przez <math>3</math>. 
Zatem <math>2|n^3-n</math> i <math>3|n^3-n</math>. Ponieważ <math>2\perp3</math>, to mamy <math>2\cdot3|n^3-n</math>.
* <math>30|n^5-n</math>:

Dowód indukcyjny. Dla <math>n=0</math> mamy <math>30|0</math>. Ponadto


<center><math>\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(n+1)(n^2+n+1)
\end{align}</math></center>


Pierwszy składnik jest podzielny przez <math>30</math> na mocy założenia indukcyjnego. 
Wystarczy więc pokazać, że i drugi składnik, czyli <math>5n(n+1)(n^2+n+1)</math> 
jest podzielny przez <math>2,3</math> i <math>5</math>.
Trywialnie <math>5|5n(n+1)(n^2+n+1)</math>. 
Ponieważ rozważany czynnik jest iloczynem między innymi dwu kolejnych liczb naturalnych, 
z których jedna jest parzysta mamy <math>2|5n(n+1)(n^2+n+1)</math>. 
W końcu zauważmy, że jeśli <math>3\not| n</math> i <math>3\not| n+1</math>, to <math>3|n^2+n+1</math>, 
co było do pokazania.
* <math>10|2^{2^n}-6</math>, dla <math>n\geqslant2</math>:

Dowód indukcyjny. Dla <math>n=2</math> mamy <math>2^{2^2}-6=16-6=10</math>, czyli <math>10|2^{2^2}</math>. 
Ponadto, gdy <math>2^{2^n}-6=10k</math>, to:


<center><math>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>


co jest oczywiście podzielne przez <math>10</math>. 

</div></div>

{{cwiczenie|3|cw 3|
Użyj algorytmu Euklidesa dla podanych wartości <math>a,b</math> do obliczenia  NWD <math>(a,b)</math>:
* <math>101,1001</math>,
* <math>55,89</math>.

}}

<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">  
* <math>101,1001</math>:

<center><math>\begin{array} {llll}
a=1001&b=101&1001=9\cdot 101+92& r=92\\
a=101&b=92&101=1\cdot 92+9& r=9\\
a=92&b=9&92=10\cdot 9+2& r=2\\
a=9&b=2&9=4\cdot 2+1& r=1\\
a=2&b=1&2=2\cdot1+0& r=0\\
a=1&b=0
\end{array} 
</math></center>

* <math>55,89</math>:

<center><math>\begin{array} {llll}
a=89&b=55&89=1\cdot 55+34& r=34\\
a=55&b=34&55=1\cdot 34+21& r=21\\
a=34&b=21&34=1\cdot 21+13& r=13\\
a=21&b=13&21=1\cdot 13+8& r=8\\
a=13&b=8&13=1\cdot8+5& r=5\\
a=8&b=5&8=1\cdot5+3& r=3\\
a=5&b=3&5=1\cdot3+2& r=2\\
a=3&b=2&3=1\cdot2+1& r=1\\
a=2&b=1&2=2\cdot1+0& r=0\\
a=1&b=0
\end{array} 
</math></center>


</div></div>

{{cwiczenie|4|cw 4|
Użyj rozszerzonego algorytmu Euklidesa dla podanych wartośći <math>a,b</math> do wskazania współczynników <math>x,y</math> takich, że NWD <math>(a,b)=xa+yb</math>:
* <math>21,111</math>,
* <math>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">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
* <math>21,111</math>:

<center><math>\begin{array} {llll}
a=111&b=21&111=5\cdot 21+6& r=6\\
a=21&b=6&21=3\cdot 6+3& r=3\\
a=6&b=3&6=2\cdot 3+0& r=0\\
a=3&b=0
\end{array} 
</math></center>


<center><math>\begin{align} 3&={\bf21}-3\cdot{\bf6}=21-3\cdot(111-5\cdot21)\\
&=-3\cdot{\bf111}+16\cdot{\bf21}
\end{align}</math></center>

* <math>25,115</math>:

<center><math>\begin{array} {llll}
a=115&b=25&115=4\cdot25+15&r=15\\
a=25&b=15&25=1\cdot15+10&r=10\\
a=15&b=10&15=1\cdot10+5&r=5\\
a=10&b=5&10=2\cdot5+0&r=0\\
a=5&b=0
\end{array} 
</math></center>


<center><math>\begin{align} 5&={\bf15}-{\bf10}=15-(25-15)\\
&=-{\bf25}+2\cdot{\bf15}=-25+2\cdot(115-4\cdot25)\\
&=2\cdot{\bf115}-9\cdot{\bf25}
\end{align}</math></center>


</div></div>

{{cwiczenie|5|cw 5|
Liczby Mersenne'a to liczby postaci <math>m_n=2^n-1</math>. 
Oto lista kilku początkowych liczb Mersenne'a z pogrubionymi liczbami pierwszymi:


<center><math>\begin{array} {|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
n&0&1&2&3&4&5&6&7&8&9&10&11&12&13\\
\hline
m_n&0&1&{\bf 3}&{\bf 7}&15&{\bf31}&63&{\bf127}&255&511&1023&2047&4095&{\bf8191}\\
\hline
\end{array} 
</math></center>


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

}}

<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">  
Spróbuj udowodnić, że jeśli <math>n</math> złożona to <math>m_n</math> złożona.
</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">  
Załóżmy, że <math>n</math> jest złożona, czyli <math>n=ab</math> dla pewnych <math>b\geq a>1</math>. Wtedy


<center><math>2^n-1=2^{ab}-1=(2^a-1)(2^{a(b-1)}+2^{a(b-2)}+\ldots+2^a+1)
</math></center>


Oba czynniki po prawej stronie są większe od <math>1</math>, zatem <math>2^n-1</math> jest złożona.
</div></div>

{{cwiczenie|6|cw 6|
Liczby Fermata to liczby postaci  <math>\mathit{fer}_{n+1}  =2^{2^n}+1</math>. 
Oto lista kilku początkowych liczb Fermata:


<center><math>\begin{array} {c|c|c|c|c|c}
n&0&1&2&3&4\\
\hline
\mathit{fer}_{n}&3&5&17&257&26987
\end{array} 
</math></center>


Pokaż, że
*  <math>\mathit{fer}_{n+1}  =\prod_{i=0}^n\mathit{fer}_{i}  +2</math>,
*  <math>\mathit{fer}_{m}  \perp  \mathit{fer}_{n}</math> , dla <math>m\neq n</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">  
Pierwszy punkt spróbuj udowodnić indukcyjnie.
W dowodzie drugiego punktu wykorzystaj ten pierwszy.
</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">  
Pierwszy wzór łatwo zweryfikować indukcyjnie.
Rzeczywiście  <math>\mathit{fer}_{1}  = 5 = 3+2 =  \mathit{fer}_{0}  +2</math>. 
Ponadto:


<center><math>\begin{align}  \mathit{fer}_{n+1}  
&=2^{2^{n+1}}+1
=2^{2^n\cdot2}+1
= \mathit{fer}_{n}  ^2-2 \mathit{fer}_{n}  +2\\
&= \mathit{fer}_{n}  ( \mathit{fer}_{n}  -2)+2
= \mathit{fer}_{n}  \cdot\prod_{i=0}^{n-1} \mathit{fer}_{i}  +2
=\prod_{i=0}^n \mathit{fer}_{i}  +2.
\end{align}</math></center>


Dla dowodu drugiego zauważmy, że przy  <math>m<n</math> punkt pierwszy daje 
<math>\mathit{fer}_{m}  | \mathit{fer}_{n}  -2</math>, czyli


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


Z drugiej strony, wprost z definicji, każda liczba Fermata jest nieparzysta, zatem


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


</div></div>

{{cwiczenie|7|cw 7|
Pokaż następujące własności liczb Fibonacci'ego:
*   NWD <math>(f_n,f_{n+1})=1</math>,
*   NWD <math>(f_m,f_n)=</math>  NWD <math>(f_{n},f_{m-n})</math>, dla <math>m>n</math>,
*   NWD <math>(f_m,f_n)= f_{NWD(n,m)}</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">  
Pierwszy punkt udowodnij indukcyjnie.<br>
W drugim wykorzystaj zależność <math>f_{a+b}=f_a f_{b+1}+f_{a-1} f_b</math>.<br>
Dla dowodu trzeciego pokaż, że   NWD <math>(f_m,f_n)=</math>  NWD <math>(f_n,f_{m \mod n}) \text{ dla } m>n</math>. 
</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">  
*   NWD <math>(f_n,f_{n+1})=1</math>:

Dla <math>n=0</math> mamy   NWD <math>(f_0,f_1)=</math>  NWD <math>(0,1)=1</math>. 
Dla <math>n=1</math> mamy   NWD <math>(f_1,f_2)=</math>  NWD <math>(1,2)=1</math>. 
Udowodnimy tezę dla <math>n+1</math> (gdzie <math>n>1</math>) przy założeniu, 
że dla mniejszych wartości jest prawdziwa. 

Niech teraz <math>d\geqslant1</math> będzie wspólnym dzielnikiem <math>f_n</math> oraz <math>f_{n+1}</math>.
Ponieważ


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


i <math>d</math> dzieli lewą stronę równości 
oraz <math>d</math> dzieli <math>f_n</math>, to musi też dzielić <math>f_{n-1}</math>.
To oznacza, że <math>d</math> jest wspólnym dzielnikiem <math>f_{n-1}</math> i <math>f_n</math>, 
co wraz z założeniem indukcyjnym   NWD <math>(f_{n-1},f_n)=1</math> daje <math>d=1</math>.
*   NWD <math>(f_m,f_n)=</math>  NWD <math>(f_{n},f_{m-n})</math>, dla <math>m>n</math>:

Niech <math>m>n</math>. 
Z zależności przytoczonej we wskazówce mamy


<center><math>f_m=f_{m-n}f_{n+1}+f_{m-n-1}f_n.\qquad(*)
</math></center>


Niech <math>d>1</math> dzieli tak <math>f_m</math> jak i <math>f_n</math>. 
Z poprzedniego punktu  mamy więc   NWD <math>(f_n,f_{n+1})=1</math>, 
czyli <math>d\perp f_{n+1}</math>. 
Ponadto,  równość <math>(*)</math> pozwala wnosić, że <math>d|f_{m-n}f_{n+1}</math>, 
co wobec <math>d\perp f_{n+1}</math> daje <math>d|f_{m-n}</math>.
Zatem dowolny <math>d>1</math> wspólny dzielnik <math>f_m</math> i <math>f_n</math> dzieli również <math>f_{m-n}</math>. 
Na odwrót, z równości <math>(*)</math>, dowolny dzielnik <math>f_{m-n}</math> i <math>f_n</math> dzieli tez <math>f_m</math>, 
więc   NWD <math>(f_m,f_n)=</math>  NWD <math>(f_n,f_{m-n})</math>.
*   NWD <math>(f_m,f_n)=f_{NWD(n,m)}</math>:

Niech <math>m>n</math> ma reprezentację  <math>m=qn+r</math>, dla pewnego <math>q\geqslant1</math> i <math>0\leq r <n</math>. 
Wtedy iterując <math>q</math> razy tożsamość 
z drugiego punktu tego zadania dostajemy:


<center><math>\begin{align}  \text{ NWD } (f_m,f_n)&= \mbox{  NWD } (f_{m-n},f_n)= \mbox{ NWD } (f_{m-2n},f_n)=\ldots\\
&= \mbox{ NWD } (f_{m-qn},f_n)= \mbox{ NWD } (f_n,f_r).
\end{align}</math></center>


Oznacza to, że indeksy liczb Fibonacciego możemy przekształcać  tak,  
jakby były poddane Algorymowi Euklidesa. 
Dzięki temu po skończonej liczbie kroków dojdziemy do indeksu   NWD <math>(m,n)</math>.

</div></div>