Matematyka dyskretna 1/Ćwiczenia 10: Teoria liczb

Teoria liczb I

Ćwiczenie 1

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

Wskazówka

Rozłóż $a$ i $b$ na czynniki pierwsze.

Rozwiązanie

Rozważmy rozkłady $a=p_1^{{\alpha }_1}\dots p_k^{{\alpha }_k}$ i $b=q_1^{{\beta }_1}\dots q_l^{{\beta }_l}$. Ponieważ $a\perp b$, to żadna liczba pierwsza nie pojawia się jednocześnie w rozkładzie $a$ i $b$. Zatem z Fundamentalnego Twierdzenia Arytmetyki o jednoznaczności rozkładu na liczby pierwsze, iloczyn

$p_1^{{\alpha }_1}\dots p_k^{{\alpha }_k}{q}_1^{{\beta }_1}\dots q_l^{{\beta }_l}=ab$

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

Ćwiczenie 2

Udowodnij, że:

• $2|n^2-n$,
• $6|n^3-n$,
• $30|n^5-n$,
• $10|2^{2^n}-6$, dla $n⩾2$.

Rozwiązanie

• $2|n^2-n$:

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

• $6|n^3-n$:

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

• $30|n^5-n$:

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

$\begin{array}{rl}(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{array}$

Pierwszy składnik jest podzielny przez $30$ na mocy założenia indukcyjnego. Wystarczy więc pokazać, że i drugi składnik, czyli $5n(n+1)(n^2+n+1)$ jest podzielny przez $2,3$ i $5$. Trywialnie $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 $2|5n(n+1)(n^2+n+1)$. W końcu zauważmy, że jeśli $3|n$ i $3|n+1$, to $3|n^2+n+1$, co było do pokazania.

• $10|2^{2^n}-6$, dla $n⩾2$:

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

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

co jest oczywiście podzielne przez $10$.

Ćwiczenie 3

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

• $101,1001$,
• $55,89$.

Rozwiązanie

• $101,1001$:

$\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\cdot 1+0& r=0\\ a=1& b=0\end{array}$

• $55,89$:

$\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\cdot 8+5& r=5\\ a=8& b=5& 8=1\cdot 5+3& r=3\\ a=5& b=3& 5=1\cdot 3+2& r=2\\ a=3& b=2& 3=1\cdot 2+1& r=1\\ a=2& b=1& 2=2\cdot 1+0& r=0\\ a=1& b=0\end{array}$

Ć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

• $21,111$:

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

$\begin{array}{rl}3& =\mathbf{𝟐}\mathbf{𝟏}-3\cdot \mathbf{𝟔}=21-3\cdot (111-5\cdot 21)\\ & =-3\cdot \mathbf{𝟏}\mathbf{𝟏}\mathbf{𝟏}+16\cdot \mathbf{𝟐}\mathbf{𝟏}\end{array}$

• $25,115$:

$\begin{array}{llll}a=115& b=25& 115=4\cdot 25+15& r=15\\ a=25& b=15& 25=1\cdot 15+10& r=10\\ a=15& b=10& 15=1\cdot 10+5& r=5\\ a=10& b=5& 10=2\cdot 5+0& r=0\\ a=5& b=0\end{array}$

$\begin{array}{rl}5& =\mathbf{𝟏}\mathbf{𝟓}-\mathbf{𝟏}\mathbf{𝟎}=15-(25-15)\\ & =-\mathbf{𝟐}\mathbf{𝟓}+2\cdot \mathbf{𝟏}\mathbf{𝟓}=-25+2\cdot (115-4\cdot 25)\\ & =2\cdot \mathbf{𝟏}\mathbf{𝟏}\mathbf{𝟓}-9\cdot \mathbf{𝟐}\mathbf{𝟓}\end{array}$

Ćwiczenie 5

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

$\begin{array}{ccccccccccccccc}n& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13\\ m_n& 0& 1& \mathbf{𝟑}& \mathbf{𝟕}& 15& \mathbf{𝟑}\mathbf{𝟏}& 63& \mathbf{𝟏}\mathbf{𝟐}\mathbf{𝟕}& 255& 511& 1023& 2047& 4095& \mathbf{𝟖}\mathbf{𝟏}\mathbf{𝟗}\mathbf{𝟏}\end{array}$

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

Wskazówka

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

Rozwiązanie

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

$2^n-1=2^{ab}-1=(2^a-1)(2^{a(b-1)}+2^{a(b-2)}+\dots +2^a+1)$

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

Ćwiczenie 6

Liczby Fermata to liczby postaci ${{f}{e}{r}}_{n+1}=2^{2^n}+1$. Oto lista kilku początkowych liczb Fermata:

$\begin{array}{cccccc}n& 0& 1& 2& 3& 4\\ {{f}{e}{r}}_n& 3& 5& 17& 257& 26987\end{array}$

Pokaż, że

• ${{f}{e}{r}}_{n+1}=\prod _{i=0}^n{{f}{e}{r}}_i+2$,
• ${{f}{e}{r}}_m\perp {{f}{e}{r}}_n$ , dla $m\ne 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 ${{f}{e}{r}}_1=5=3+2={{f}{e}{r}}_0+2$. Ponadto:

$\begin{array}{rl}{{f}{e}{r}}_{n+1}& =2^{2^{n+1}}+1=2^{2^n\cdot 2}+1={{f}{e}{r}}_n^2-2{{f}{e}{r}}_n+2\\ & ={{f}{e}{r}}_n({{f}{e}{r}}_n-2)+2={{f}{e}{r}}_n\cdot \prod _{i=0}^{n-1}{{f}{e}{r}}_i+2=\prod _{i=0}^n{{f}{e}{r}}_i+2.\end{array}$

Dla dowodu drugiego zauważmy, że przy $m<n$ punkt pierwszy daje ${{f}{e}{r}}_m|{{f}{e}{r}}_n-2$, czyli

${{f}{e}{r}}_{n}mod{{f}{e}{r}}_m=2$

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

NWD $({{f}{e}{r}}_n,{{f}{e}{r}}_m)=$ NWD $({{f}{e}{r}}_m,2)=1$

Ćwiczenie 7

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

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

Wskazówka

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

Rozwiązanie

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

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

Niech teraz $d⩾1$ będzie wspólnym dzielnikiem $f_n$ oraz $f_{n+1}$. Ponieważ

$f_{n+1}=f_{n-1}+f_n$

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

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

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

$f_m=f_{m-n}{f}_{n+1}+f_{m-n-1}{f}_n.(*)$

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

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

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

$\begin{array}{rl}\text{ NWD }(f_m,f_n)& =\text{ NWD }(f_{m-n},f_n)=\text{ NWD }(f_{m-2n},f_n)=\dots \\ & =\text{ NWD }(f_{m-qn},f_n)=\text{ NWD }(f_n,f_r).\end{array}$

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