Matematyka dyskretna 1/Ćwiczenia 10: Teoria liczb

Teoria liczb I

Ćwiczenie 1

Udowodnij, że dla $a, b, n \in ℕ$ , jeśli $a | n$ , $b | n$ i $a ⊥ b$ , to $a b | n$ .

Wskazówka

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

Rozwiązanie

Rozważmy rozkłady $a = p_{1}^{α_{1}} \dots p_{k}^{α_{k}}$ i $b = q_{1}^{β_{1}} \dots q_{l}^{β_{l}}$ . Ponieważ $a ⊥ 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}^{α_{1}} \dots p_{k}^{α_{k}} q_{1}^{β_{1}} \dots q_{l}^{β_{l}} = a b

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

$30 | n^{5} - n$ :

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

\begin{aligned} (n + 1)^{5} - (n + 1) & = (n^{5} + 5 n^{4} + 10 n^{3} + 10 n^{2} + 5 n + 1) - (n + 1) \\ = (n^{5} - n) + (5 n^{4} + 10 n^{3} + 10 n^{2} + 5 n) \\ = (n^{5} - n) + 5 n (n + 1) (n^{2} + n + 1) \end{aligned}

Pierwszy składnik jest podzielny przez $30$ na mocy założenia indukcyjnego. Wystarczy więc pokazać, że i drugi składnik, czyli $5 n (n + 1) (n^{2} + n + 1)$ jest podzielny przez $2, 3$ i $5$ . Trywialnie $5 | 5 n (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 | 5 n (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 = 10 k$ , to:

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

= 100 k^{2} + 120 k + 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) = x a + y b$ :

$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{aligned} 3 & = 𝟐 𝟏 - 3 \cdot 𝟔 = 21 - 3 \cdot (111 - 5 \cdot 21) \\ = - 3 \cdot 𝟏 𝟏 𝟏 + 16 \cdot 𝟐 𝟏 \end{aligned}

$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{aligned} 5 & = 𝟏 𝟓 - 𝟏 𝟎 = 15 - (25 - 15) \\ = - 𝟐 𝟓 + 2 \cdot 𝟏 𝟓 = - 25 + 2 \cdot (115 - 4 \cdot 25) \\ = 2 \cdot 𝟏 𝟏 𝟓 - 9 \cdot 𝟐 𝟓 \end{aligned}

Ć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 & 𝟑 & 𝟕 & 15 & 𝟑 𝟏 & 63 & 𝟏 𝟐 𝟕 & 255 & 511 & 1023 & 2047 & 4095 & 𝟖 𝟏 𝟗 𝟏 \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 = a b$ dla pewnych $b \geq a > 1$ . Wtedy

2^{n} - 1 = 2^{a b} - 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} ⊥ {f e r}_{n}$ , dla $m \neq n$ .

Wskazówka

Rozwiązanie

Pierwszy wzór łatwo zweryfikować indukcyjnie. Rzeczywiście ${f e r}_{1} = 5 = 3 + 2 = {f e r}_{0} + 2$ . Ponadto:

\begin{aligned} {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{aligned}

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_{N W D (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_{m mod n}) 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 ⊥ f_{n + 1}$ . Ponadto, równość $(*)$ pozwala wnosić, że $d | f_{m - n} f_{n + 1}$ , co wobec $d ⊥ 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_{N W D (n, m)}$ :

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

\begin{aligned} NWD (f_{m}, f_{n}) & = NWD (f_{m - n}, f_{n}) = NWD (f_{m - 2 n}, f_{n}) = \dots \\ = NWD (f_{m - q n}, f_{n}) = NWD (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 $(m, n)$ .

Matematyka dyskretna 1/Ćwiczenia 10: Teoria liczb

Teoria liczb I

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia