Matematyka dyskretna 1/Ćwiczenia 10: Teoria liczb

Teoria liczb I

Ćwiczenie ex tl cwiczenie - podobne podzielnosc wzglednie pierwszych liczb

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 ex tl podzielności

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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\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 ex tl zapuszczenie Euklidesa

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 ex tl rozszerzony algorytm Euklidesa

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

Wskazówka

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}}$ Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned 3&={\bf21}-3\cdot{\bf6}=21-3\cdot(111-5\cdot21)\\ &=-3\cdot{\bf111}+14\cdot{\bf21} \endaligned}

• $\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}}$ Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 ex tl cwiczenie - liczby Mersenne'a

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 ex tl liczby Fermata

Liczby Fermata to liczby postaci Parser nie mógł rozpoznać (nieznana funkcja „\textsl”): {\displaystyle \displaystyle \textsl{fer}_{n+1}\displaystyle =2^{2^n}+1} . Oto lista kilku początkowych liczb Fermata:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \displaystyle \begin{array} {c|c|c|c|c|c} n&0&1&2&3&4\\ \hline \mbox{} fer_{n}Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle } &3&5&17&257&26987 \end{array} }

Pokaż, że

• Parser nie mógł rozpoznać (nieznana funkcja „\textsl”): {\displaystyle \displaystyle \textsl{fer}_{n+1}\displaystyle =\prod_{i=0}^n \displaystyle \textsl{fer}_{i}\displaystyle +2} ,
• Parser nie mógł rozpoznać (nieznana funkcja „\textsl”): {\displaystyle \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 Parser nie mógł rozpoznać (nieznana funkcja „\textsl”): {\displaystyle \displaystyle \textsl{fer}_{1}\displaystyle = 5 = 3+2 = \displaystyle \textsl{fer}_{0}\displaystyle +2} . Ponadto:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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

Parser nie mógł rozpoznać (nieznana funkcja „\textsl”): {\displaystyle \displaystyle \textsl{fer}_{m}\displaystyle   |  \displaystyle \textsl{fer}_{n}\displaystyle   -2}
, czyli

Parser nie mógł rozpoznać (nieznana funkcja „\textsl”): {\displaystyle \displaystyle \textsl{fer}_{n}} { mod} Parser nie mógł rozpoznać (nieznana funkcja „\textsl”): {\displaystyle \displaystyle \textsl{fer}_{m}\displaystyle =2. }

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

NWD Parser nie mógł rozpoznać (nieznana funkcja „\textsl”): {\displaystyle \displaystyle ( \displaystyle \textsl{fer}_{n}\displaystyle , \displaystyle \textsl{fer}_{m}\displaystyle )= } NWD Parser nie mógł rozpoznać (nieznana funkcja „\textsl”): {\displaystyle \displaystyle ( \displaystyle \textsl{fer}_{m}\displaystyle ,2)=1. }

Ćwiczenie ex tl liczby Fibonacciego

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (f_m,f_n)=f_{ } NWD Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (f_n,f_{m } { mod} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (f_m,f_n)=f_{ } NWD Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (m,n)}} :

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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned } NWD Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (f_m,f_n)&= } NWD $\displaystyle (f_{m-n},f_{n})=$ NWD Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (f_{m-2n},f_n)=\ldots\\ &= } NWD $\displaystyle (f_{m-qn},f_{n})=$ NWD Parser nie mógł rozpoznać (nieznana funkcja „\endaligned”): {\displaystyle \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)$.