Matematyka dyskretna 1/Ćwiczenia 10: Teoria liczb

From Studia Informatyczne

Teoria liczb I

Ćwiczenie 1

Udowodnij, że dla \displaystyle a,b,n\in\mathbb{N}, jeśli \displaystyle a|n, \displaystyle b|n i \displaystyle a\perp b, to \displaystyle ab|n.

Wskazówka

Rozłóż \displaystyle a i \displaystyle b na czynniki pierwsze.

Rozwiązanie

Rozważmy rozkłady \displaystyle a=p_1^{\alpha_1}\ldots p_k^{\alpha_k} i \displaystyle b=q_1^{\beta_1}\ldots q_l^{\beta_l}. Ponieważ \displaystyle a\perp b, to żadna liczba pierwsza nie pojawia się jednocześnie w rozkładzie \displaystyle a i \displaystyle b. Zatem z Fundamentalnego Twierdzenia Arytmetyki o jednoznaczności rozkładu na liczby pierwsze, iloczyn


\displaystyle p_1^{\alpha_1}\ldots p_k^{\alpha_k}q_1^{\beta_1}\ldots q_l^{\beta_l}=ab


musi wystąpić w rozkładzie liczby \displaystyle n.

Ćwiczenie 2

Udowodnij, że:

  • \displaystyle 2|n^2-n,
  • \displaystyle 6|n^3-n,
  • \displaystyle 30|n^5-n,
  • \displaystyle 10|2^{2^n}-6, dla \displaystyle n\geqslant2.

Rozwiązanie

  • \displaystyle 2|n^2-n:

Mamy \displaystyle n^2-n=n(n-1) i jedna spośród dwu kolejnych liczb naturalnych \displaystyle n-1,n jest parzysta, zatem i ich iloczyn jest parzysty.

  • \displaystyle 6|n^3-n:

Mamy \displaystyle n^3-n=n(n^2-1)=n(n-1)(n+1) i przynajmniej jedna z trzech kolejnych liczb \displaystyle n-1,n,n+1 jest podzielna przez \displaystyle 2 i przynajmniej jedna jest podzielna przez \displaystyle 3. Zatem \displaystyle 2|n^3-n i \displaystyle 3|n^3-n. Ponieważ \displaystyle 2\perp3, to mamy \displaystyle 2\cdot3|n^3-n.

  • \displaystyle 30|n^5-n:

Dowód indukcyjny. Dla \displaystyle n=0 mamy \displaystyle 30|0. Ponadto


\displaystyle \aligned (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). \endaligned


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

  • \displaystyle 10|2^{2^n}-6, dla \displaystyle n\geqslant2:

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


\displaystyle 2^{2^{n+1}}-6=2^{2^n\cdot2}-6=(10k+6)^2-6=(100k^2+120k+36)-6=100k^2+120k+30,


co jest oczywiście podzielne przez \displaystyle 10.

Ćwiczenie 3

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

  • \displaystyle 101,1001,
  • \displaystyle 55,89.

Rozwiązanie

  • \displaystyle 101,1001:
\displaystyle \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}
  • \displaystyle 55,89:
\displaystyle \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}


Ćwiczenie 4

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

  • \displaystyle 21,111,
  • \displaystyle 25,115.

Rozwiązanie

  • \displaystyle 21,111:
\displaystyle \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}


\displaystyle \aligned 3&={\bf21}-3\cdot{\bf6}=21-3\cdot(111-5\cdot21)\\ &=-3\cdot{\bf111}+16\cdot{\bf21} \endaligned
  • \displaystyle 25,115:
\displaystyle \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}


\displaystyle \aligned 5&={\bf15}-{\bf10}=15-(25-15)\\ &=-{\bf25}+2\cdot{\bf15}=-25+2\cdot(115-4\cdot25)\\ &=2\cdot{\bf115}-9\cdot{\bf25} \endaligned


Ćwiczenie 5

Liczby Mersenne'a to liczby postaci \displaystyle m_n=2^n-1. Oto lista kilku początkowych liczb Mersenne'a z pogrubionymi liczbami pierwszymi:


\displaystyle \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}


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

Wskazówka

Spróbuj udowodnić, że jeśli \displaystyle n złożona to \displaystyle m_n złożona.

Rozwiązanie

Załóżmy, że \displaystyle n jest złożona, czyli \displaystyle n=ab dla pewnych \displaystyle b\geq a>1. Wtedy


\displaystyle 2^n-1=2^{ab}-1=(2^a-1)(2^{a(b-1)}+2^{a(b-2)}+\ldots+2^a+1)


Oba czynniki po prawej stronie są większe od \displaystyle 1, zatem \displaystyle 2^n-1 jest złożona.

Ćwiczenie 6

Liczby Fermata to liczby postaci \displaystyle \textsl{fer}_{n+1}\displaystyle   =2^{2^n}+1. Oto lista kilku początkowych liczb Fermata:


\displaystyle \begin{array} {c|c|c|c|c|c} n&0&1&2&3&4\\ \hline \textsl{fer}_{n}&3&5&17&257&26987 \end{array}


Pokaż, że

  • \displaystyle \textsl{fer}_{n+1}\displaystyle   =\prod_{i=0}^n \displaystyle \textsl{fer}_{i}\displaystyle   +2,
  • \displaystyle \textsl{fer}_{m}\displaystyle   \perp   \displaystyle \textsl{fer}_{n} , dla \displaystyle m\neq n.

Wskazówka

Pierwszy punkt spróbuj udowodnić indukcyjnie. W dowodzie drugiego punktu wykorzystaj ten pierwszy.

Rozwiązanie

Pierwszy wzór łatwo zweryfikować indukcyjnie. Rzeczywiście \displaystyle \textsl{fer}_{1}\displaystyle   = 5 = 3+2 =   \displaystyle \textsl{fer}_{0}\displaystyle   +2. Ponadto:


\displaystyle \aligned   \displaystyle \textsl{fer}_{n+1}\displaystyle    &=2^{2^{n+1}}+1 =2^{2^n\cdot2}+1 =  \displaystyle \textsl{fer}_{n}\displaystyle   ^2-2  \displaystyle \textsl{fer}_{n}\displaystyle   +2\\ &=  \displaystyle \textsl{fer}_{n}\displaystyle   (  \displaystyle \textsl{fer}_{n}\displaystyle   -2)+2 =  \displaystyle \textsl{fer}_{n}\displaystyle   \cdot\prod_{i=0}^{n-1}  \displaystyle \textsl{fer}_{i}\displaystyle   +2 =\prod_{i=0}^n  \displaystyle \textsl{fer}_{i}\displaystyle   +2. \endaligned


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


\displaystyle \textsl{fer}_{n} \mod \displaystyle \textsl{fer}_{m}\displaystyle   =2.


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


NWD \displaystyle  (  \displaystyle \textsl{fer}_{n}\displaystyle   ,  \displaystyle \textsl{fer}_{m}\displaystyle   )= NWD \displaystyle  (  \displaystyle \textsl{fer}_{m}\displaystyle   ,2)=1.


Ćwiczenie 7

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

  • NWD \displaystyle  (f_n,f_{n+1})=1,
  • NWD \displaystyle  (f_m,f_n)= NWD \displaystyle  (f_{n},f_{m-n}), dla \displaystyle m>n,
  • NWD \displaystyle  (f_m,f_n)=f_{ NWD \displaystyle (m,n)}.

Wskazówka

Pierwszy punkt udowodnij indukcyjnie.
W drugim wykorzystaj zależność \displaystyle f_{a+b}=f_a f_{b+1}+f_{a-1} f_b.
Dla dowodu trzeciego pokaż, że NWD \displaystyle  (f_m,f_n)= NWD \displaystyle  (f_n,f_{m \mod \displaystyle   n}), dla \displaystyle m>n.

Rozwiązanie

  • NWD \displaystyle  (f_n,f_{n+1})=1:

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

Niech teraz \displaystyle d\geqslant1 będzie wspólnym dzielnikiem \displaystyle f_n oraz \displaystyle f_{n+1}.

Ponieważ


\displaystyle f_{n+1}=f_{n-1}+f_n.


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

  • NWD \displaystyle  (f_m,f_n)= NWD \displaystyle  (f_{n},f_{m-n}), dla \displaystyle m>n:

Niech \displaystyle m>n. Z zależności przytoczonej we wskazówce mamy


\displaystyle f_m=f_{m-n}f_{n+1}+f_{m-n-1}f_n.\qquad(*)


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

  • NWD \displaystyle  (f_m,f_n)=f_{ NWD \displaystyle  (m,n)}:

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


\displaystyle \aligned  \textrm{ NWD } \displaystyle  (f_m,f_n)&= \textrm{  NWD } \displaystyle  (f_{m-n},f_n)= \textrm{ NWD } \displaystyle  (f_{m-2n},f_n)=\ldots\\ &= \textrm{ NWD } \displaystyle  (f_{m-qn},f_n)= \textrm{ NWD } \displaystyle  (f_n,f_r). \endaligned


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 \displaystyle  (m,n).