Matematyka dyskretna 1/Ćwiczenia 10: Teoria liczb

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\geqslant 2$.

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\perp 3$, to mamy $\displaystyle 2\cdot 3|n^{3}-n$.

• $\displaystyle 30|n^{5}-n$:

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

$\displaystyle {\begin{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).\end{aligned}}$

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\geqslant 2$:

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}\cdot 2}-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\cdot 1+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\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 $\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 {\begin{aligned}3&={\bf {21}}-3\cdot {\bf {6}}=21-3\cdot (111-5\cdot 21)\\&=-3\cdot {\bf {111}}+16\cdot {\bf {21}}\end{aligned}}$

• $\displaystyle 25,115$:

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

$\displaystyle {\begin{aligned}5&={\bf {15}}-{\bf {10}}=15-(25-15)\\&=-{\bf {25}}+2\cdot {\bf {15}}=-25+2\cdot (115-4\cdot 25)\\&=2\cdot {\bf {115}}-9\cdot {\bf {25}}\end{aligned}}$

Ć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&{\bf {31}}&63&{\bf {127}}&255&511&1023&2047&4095&{\bf {8191}}\\\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 {\mathit {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 {\mathit {fer}}_{n}&3&5&17&257&26987\end{array}}$

Pokaż, że

• $\displaystyle {\mathit {fer}}_{n+1}\displaystyle =\prod _{i=0}^{n}\displaystyle {\mathit {fer}}_{i}\displaystyle +2$,
• $\displaystyle {\mathit {fer}}_{m}\displaystyle \perp \displaystyle {\mathit {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 {\mathit {fer}}_{1}\displaystyle =5=3+2=\displaystyle {\mathit {fer}}_{0}\displaystyle +2$. Ponadto:

$\displaystyle {\begin{aligned}\displaystyle {\mathit {fer}}_{n+1}\displaystyle &=2^{2^{n+1}}+1=2^{2^{n}\cdot 2}+1=\displaystyle {\mathit {fer}}_{n}\displaystyle ^{2}-2\displaystyle {\mathit {fer}}_{n}\displaystyle +2\\&=\displaystyle {\mathit {fer}}_{n}\displaystyle (\displaystyle {\mathit {fer}}_{n}\displaystyle -2)+2=\displaystyle {\mathit {fer}}_{n}\displaystyle \cdot \prod _{i=0}^{n-1}\displaystyle {\mathit {fer}}_{i}\displaystyle +2=\prod _{i=0}^{n}\displaystyle {\mathit {fer}}_{i}\displaystyle +2.\end{aligned}}$

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

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

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

NWD $\displaystyle (\displaystyle {\mathit {fer}}_{n}\displaystyle ,\displaystyle {\mathit {fer}}_{m}\displaystyle )=$ NWD $\displaystyle (\displaystyle {\mathit {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(n,m)}$.

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 n}){\text{ dla }}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\geqslant 1$ 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(n,m)}$:

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

$\displaystyle {\begin{aligned}{\text{ NWD }}\displaystyle (f_{m},f_{n})&={\mbox{ NWD }}\displaystyle (f_{m-n},f_{n})={\mbox{ NWD }}\displaystyle (f_{m-2n},f_{n})=\ldots \\&={\mbox{ NWD }}\displaystyle (f_{m-qn},f_{n})={\mbox{ NWD }}\displaystyle (f_{n},f_{r}).\end{aligned}}$

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)$.