8. Dowody dotyczące podzielności liczb całkowitych

R1364Zx2JtSVJ

Okazuje się, że w zbiorze liczb całkowitych można udowodnić mnóstwo twierdzeń dotyczących podzielności.

Niektóre z zaprezentowanych tutaj własności będą wręcz oczywiste, inne zaskakujące. Przy okazji wspomnimy postać Diofantosa – greckiego matematyka żyjącego w III wieku n.e. w Aleksandrii, na pamiątkę którego pewien typ równań nazywamy równaniami diofantycznymi...

Twoje cele

Udowodnisz twierdzenia dotyczące podzielności w zbiorze liczb całkowitych.
Wykorzystasz własności podzielności w zbiorze liczb całkowitych.

W tej lekcji zajmiemy się głównie dowodzeniem twierdzeń.

Przykład 1

Udowodnimy, że dla dowolnej liczby całkowitej $n$ liczba $n^{2} - n$ jest parzysta.

Sprawdźmy najpierw na kilku przykładach, czy teza tego twierdzenia jest spełniona:

Liczba całkowita $n$	Wartość wyrażenia $n^{2} - n$	Odpowiedź
$4$	$4^{2} - 4 = 12$	$2 \| 12$
$3$	$3^{2} - 3 = 6$	$2 \| 6$
$0$	$0^{2} - 0 = 0$	$2 \| 0$
$- 5$	${(- 5)}^{2} - (- 5) = 30$	$2 \| 30$
$- 6$	${(- 6)}^{2} - (- 6) = 36$	$2 \| 36$

We wszystkich sprawdzonych przypadkach teza jest spełniona, ale nawet gdybyśmy sprawdzili dużo więcej liczb naturalnych $n$ , nie byłby to dowód twierdzenia.

Potrzebujemy rozważania ogólnego.

Dowód:

Zauważmy, że $n^{2} - n = n (n - 1)$ , co oznacza, że $n^{2} - n$ jest iloczynem dwóch kolejnych liczb całkowitych.

Ponieważ co druga liczba całkowita jest parzysta, więc dokładnie jedna z liczb $n$ i $n - 1$ jest podzielna przez $2$ .

Iloczyn liczby parzystej przez dowolną liczbę całkowitą jest parzysty, zatem liczba $n (n - 1) = n^{2} - n$ również jest parzysta.

Przykład 2

Udowodnimy, że dla dowolnej liczby całkowitej $n$ liczba $n^{3} - n$ jest podzielna przez $6$ .

Ponownie sprawdzimy tezę twierdzenia dla kilku liczb całkowitych $n$ :

Liczba całkowita $n$	Wartość wyrażenia $n^{3} - n$	Odpowiedź
$4$	$4^{3} - 4 = 60$	$6 \| 60$
$3$	$3^{3} - 3 = 24$	$6 \| 24$
$0$	$0^{3} - 0 = 0$	$6 \| 0$
$- 5$	${(- 5)}^{3} - (- 5) = - 120$	$6 \| (- 120)$
$- 6$	${(- 6)}^{3} - (- 6) = - 210$	$6 \| (- 210)$

Dla rozważanych liczb teza jest spełniona. Potrzebujemy jednak dowodu.

Dowód:

Zauważmy, że $n^{3} - n = n (n^{2} - 1) = n (n - 1) (n + 1)$ – przy tym przekształceniu skorzystaliśmy ze wzoru skróconego mnożenia $a^{2} - b^{2} = (a - b) (a + b)$ .

Zatem rozważane wyrażenie jest iloczynem trzech kolejnych liczb całkowitych: $n - 1$ , $n$ , $n + 1$ .

Wśród trzech kolejnych liczb całkowitych przynajmniej jedna jest parzysta (albo jest to liczba $n$ , albo liczby $n - 1$ i $n + 1$ ).

Ponadto wśród trzech kolejnych liczb całkowitych dokładnie jedna dzieli się przez $3$ .

Ponieważ liczby $2$ i $3$ są względnie pierwsze, to iloczyn liczb, z których jedna jest podzielna przez $2$ i jedna jest podzielna przez $3$ , dzieli się przez $6$ .

Przykład 3

Udowodnimy, że równanie $x^{3} - x - 1111 = 0$ nie jest spełnione przez żadną liczbę całkowitą.

Dowód:

Zauważmy, że podane równanie można przekształcić do postaci $x (x - 1) (x + 1) = 1111$ .

Dla dowolnej liczby całkowitej $x$ lewa strona równania jest iloczynem trzech kolejnych liczb całkowitych, co oznacza, że jest podzielna przez $3$ .

Prawa strona równania nie dzieli się przez $3$ , zatem otrzymujemy sprzeczność, bo liczba podzielna przez $3$ nie może być równa liczbie niepodzielnej przez $3$ .

Oznacza to, że wyjściowe równanie nie jest spełnione przez żadną liczbę całkowitą.

RfbcWDt84BrDq1

Ilustracja przedstawia popiersie młodego mężczyzny w starożytnej szacie. Mężczyzna ma krótko obcięte włosy, patrzy w prawo, marszcząc brwi. — Diofantos
Źródło: nieznany, dostępny w internecie: www.ru.wikipedia.org.

Powyższe równanie jest przykładem równania diofantycznegorównanie diofantycznerównania diofantycznego, czyli równania, którego rozwiązań szukamy w zbiorze liczb całkowitych (lub jego podzbiorach). Równania diofantyczne swoją zawdzięczają greckiemu matematykowi z III wieku n.e. DiofantosDiofantosDiofantos jest znany głównie ze swojego dzieła Arytmetyka, w którym opisywał sposoby rozwiązywania równań i zadań tekstowych prowadzących do równań.

Uważany jest za ojca języka algebraicznego, choć swoje zadania rozwiązywał głównie opisowo.

Przykład 4

Wykażemy, że różnica czwartych potęg dwóch liczb całkowitych różniących się o $2$ jest podzielna przez $16$ .

Dowód:

Mamy do wykazania, że dla dowolnej liczby całkowitej $n$ , $n^{4} - {(n - 2)}^{4}$ dzieli się przez $16$ .

Korzystając ze wzoru $a^{2} - b^{2} = (a - b) (a + b)$ możemy wykonać następujące przekształcenia

$n^{4} - {(n - 2)}^{4} = {[n^{2}]}^{2} - {[{(n - 2)}^{2}]}^{2} = [n^{2} - {(n - 2)}^{2}] \cdot [n^{2} + {(n - 2)}^{2}] =$

$= [n - (n - 2)] \cdot [n + (n - 2)] \cdot [n^{2} + {(n - 2)}^{2}] =$

$= 2 \cdot (2 n - 2) \cdot [n^{2} + {(n - 2)}^{2}] =$

Korzystając ze wzoru:

{(a - b)}^{2} = a^{2} - 2 a b + b^{2}

możemy kontynuować przekształcanie:

$= 4 \cdot (n - 1) (n^{2} + n^{2} - 4 n + 4) = 4 \cdot (n - 1) (2 n^{2} - 4 n + 4) =$

$= 8 \cdot (n - 1) (n^{2} - 2 n + 2)$

Zauważmy teraz, że jeśli $n$ jest liczbą nieparzystą, to liczba $n - 1$ jest liczbą parzystą.

Zaś jeśli $n$ jest liczbą parzystą, to $n^{2} - 2 n + 2$ jest liczbą parzystą.

Zatem niezależnie od parzystości liczby $n$ któryś z nawiasów $(n - 1)$ lub $(n^{2} - 2 n + 2)$ jest parzysty. Iloczyn liczby parzystej i liczby $8$ jest podzielny przez $16$ .

Ważne!

Iloczyn kolejnych liczb naturalnych począwszy od liczby $1$ do liczby $n$ oznaczamy $n!$ i czytamy $n$ silniasilniasilnia.

Na przykład: $1! = 1$ , $3! = 1 \cdot 2 \cdot 3 = 6$ , $6! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 = 720$ .

Przykład 5

Udowodnimy, że liczba $26!$ dzieli się przez $1000000$ .

Dowód:

Liczba $26!$ to iloczyn kolejnych liczb naturalnych od $1$ do $26$ .

Wśród czynników znajdują się liczby $5$ , $10$ , $15$ , $20$ i $25$ oraz liczby $2$ , $4$ i $6$ .

Iloczyn wybranych czynników to $(5 \cdot 2) \cdot (15 \cdot 6) \cdot (25 \cdot 4) \cdot (10 \cdot 20) = 10 \cdot 90 \cdot 100 \cdot 200 = 18000000$ .

Ponieważ spośród czynników liczby $26!$ można wybrać takie, których iloczyn jest równy liczbie $18000000$ , która jest podzielna przez $1000000$ , więc liczba $26!$ również jest podzielna przez $1000000$ .

Przykład 6

Udowodnimy, że liczba $3^{15} + 3^{16} + 3^{17}$ jest podzielna przez $13$ .

Dowód:

Wykonajmy następujące przekształcenia:

$3^{15} + 3^{16} + 3^{17} = 3^{15} + 3^{1 + 15} + 3^{2 + 15} = 3^{15} + 3 \cdot 3^{15} + 3^{2} \cdot 3^{15} =$

$= 3^{15} \cdot (1 + 3 + 9) = 3^{15} \cdot 13$

Ponieważ liczba $3^{15}$ jest całkowita, więc iloczyn $3^{15} \cdot 13$ jest liczbą podzielną przez $13$ .

Polecenie 1

Przeanalizuj dowody twierdzeń zawarte w poniższej animacji.

R1aDrU4K9r3x1

Polecenie 2

Udowodnij twierdzenie:

Jeżeli suma cyfry jedności, podwojonej cyfry dziesiątek i czterokrotności cyfry setek liczby naturalnej trzycyfrowej dzieli się przez $8$ , to ta liczba dzieli się przez $8$ .

Z założenia wiemy, że liczba $c + 2 b + 4 a$ dzieli się przez $8$ , gdzie $a$ , $b$ , $c$ są kolejno cyframi setek, dziesiątek i jedności liczby $\bar{a b c}$ .

Zauważmy, że:

$\bar{a b c} = 100 a + 10 b + c = 96 a + 4 a + 8 b + 2 b + c = 96 a + 8 b + 4 a + 2 b + c =$

$= 8 \cdot (12 a + b) + 4 a + 2 b + c$

Ponieważ liczba $12 a + b$ jest całkowita, więc $8 \cdot (12 a + b)$ dzieli się przez $8$ .

Ponadto z założenia wiadomo, że $4 a + 2 b + c$ dzieli się przez $8$ .

Zatem liczba $\bar{a b c} = 100 a + 10 b + c$ dzieli się przez $8$ jako suma liczb podzielnych przez $8$ . QED.

Polecenie 3

RL3tEFFVcgXUA

Pokaż ćwiczenia:

Ćwiczenie 1

Wykaż, że iloczyn trzech kolejnych liczb podzielnych przez $3$ dzieli się przez $81$ .

Zauważmy, że trzy kolejne liczby podzielne przez $3$ możemy zapisać w postaci:

$3 n$ , $3 n + 3$ , $3 n + 6$

gdzie:
$n$ – jest liczbą całkowitą.

Rozważmy ich iloczyn $3 n (3 n + 3) (3 n + 6)$ .

Z każdego z nawiasów możemy wyłączyć liczbę $3$ otrzymując:

$3 n \cdot 3 \cdot (n + 1) \cdot 3 \cdot (n + 2) = 27 n (n + 1) (n + 2)$

Ponieważ liczby $n$ , $n + 1$ , $n + 2$ to trzy kolejne liczby całkowite, więc dokładnie jedna z nich dzieli się przez $3$ .

Iloczyn liczby podzielnej przez $3$ i liczby $27$ jest podzielny przez $81$ .

Ćwiczenie 2

Wykaż, że jeżeli $n$ jest liczbą nieparzystą to liczba $(n - 1) (n + 1) (n + 3)$ jest liczbą podzielną przez $48$ .

Ponieważ $n$ jest liczbą nieparzystą, więc jest postaci:

$n = 2 k + 1$

gdzie:
$k$ – jest liczbą całkowitą.

Zatem:

$(n - 1) (n + 1) (n + 3) = (2 k + 1 - 1) (2 k + 1 + 1) (2 k + 1 + 3) =$

$= 2 k (2 k + 2) (2 k + 4) = 2 k \cdot 2 \cdot (k + 1) \cdot 2 \cdot (k + 2) = 8 k (k + 1) (k + 2)$

Poniewaz liczby $k$ , $k + 1$ , $k + 2$ to trzy kolejne liczby całkowite, więc dokładnie jedna z nich dzieli się przez $3$ i przynajmniej jedna dzieli się przez $2$ , co oznacza, że ich iloczyn dzieli się przez $6$ .

Iloczyn liczby podzielnej przez $6$ i liczby $8$ jest podzielny przez $48$ .

Ćwiczenie 3

Wykaż, że liczba $2^{13} + 2^{15} + 2^{17}$ jest podzielna przez $21$ .

Wyrażenie $2^{13} + 2^{15} + 2^{17}$ możemy przekształcić następująco

$2^{13} + 2^{15} + 2^{17} = 2^{13} + 2^{13 + 2} + 2^{13 + 4} = 2^{13} + 2^{13} \cdot 2^{2} + 2^{13} \cdot 2^{4} =$

$= 2^{13} \cdot (1 + 2^{2} + 2^{4}) = 2^{13} \cdot (1 + 4 + 16) = 2^{13} \cdot 21$

Ponieważ $2^{13}$ jest liczbą naturalną, więc $2^{13} \cdot 21$ jest liczbą podzielną przez $21$ .

R1SBFcjkd1tIw2

Ćwiczenie 4

Ćwiczenie 5

Udowodnij, że liczba $16!$ jest podzielna przez $2^{15}$ .

Liczba $16!$ to iloczyn kolejnych liczb naturalnych od $1$ do $16$ .

Występują w nim następujące liczby parzyste:

$2$ , $4 = 2^{2}$ , $6 = 2 \cdot 3$ , $8 = 2^{3}$ , $10 = 2 \cdot 5$ , $12 = 2^{2} \cdot 3$ , $14 = 2 \cdot 7$ , $16 = 2^{4}$

Po wymnożeniu tych liczb otrzymamy liczbę $2$ w potędze o wykładniku $15$ , czyli $2^{15}$ pomnożoną przez liczby nieparzyste.

Oznacza to nie tylko, że liczba $16!$ dzieli się przez $2^{15}$ , ale również, że $2^{15}$ jest maksymalną potęgą dwójki będącą dzielnikiem $16!$ .

RT7NZ08GWF5Bf2

Ćwiczenie 6

Rj1jUn6YeYUVb2

Ćwiczenie 7

Ćwiczenie 8

Wykaż, że równanie $6 x^{2} + 14 = 21 y^{2}$ nie ma rozwiązań całkowitych.

Przekształćmy równanie do postaci $14 = 21 y^{2} - 6 x^{2}$ , co jest równoważne $14 = 3 \cdot (7 y^{2} - 2 x^{2})$ .

Zauważmy, że jeśli liczby $x$ i $y$ są całkowite, to ich kwadraty również są liczbami całkowitymi.

Ponieważ iloczyn i różnica liczb całkowitych są liczbami całkowitymi, więc po prawej stronie równości znajduje się liczba całkowita podzielna przez $3$ .

Liczba $14$ nie dzieli się przez $3$ , zatem równanie jest sprzeczne.

R1ayxPJnh9Wvu31

Ćwiczenie 9

Wykaż, że liczba nawias, jeden, plus, dwa tysiące trzynaście indeks górny, dwa, koniec indeksu górnego, zamknięcie nawiasu, nawias, jeden, plus, dwa tysiące trzynaście indeks górny, cztery, koniec indeksu górnego, zamknięcie nawiasu jest dzielnikiem liczby jeden, plus, dwa tysiące trzynaście, plus, dwa tysiące trzynaście indeks górny, dwa, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, trzy, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, cztery, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, pięć, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, sześć, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, siedem, koniec indeksu górnego.
Uporządkuj poniższe wypowiedzi, aby otrzymać dowód powyższego twierdzenia. Elementy do uszeregowania: 1. W drugim nawiasie również możemy połączyć składniki w pary:
nawias, jeden, plus, dwa tysiące trzynaście indeks górny, dwa, koniec indeksu górnego, zamknięcie nawiasu, razy, nawias kwadratowy, nawias, jeden, plus, dwa tysiące trzynaście, zamknięcie nawiasu, plus, nawias, dwa tysiące trzynaście indeks górny, cztery, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, pięć, koniec indeksu górnego, zamknięcie nawiasu, zamknięcie nawiasu kwadratowego., 2. Połączmy składniki w pary:
nawias, jeden, plus, dwa tysiące trzynaście indeks górny, dwa, koniec indeksu górnego, zamknięcie nawiasu, plus, nawias, dwa tysiące trzynaście, plus, dwa tysiące trzynaście indeks górny, trzy, koniec indeksu górnego, zamknięcie nawiasu, plus, nawias, dwa tysiące trzynaście indeks górny, cztery, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, sześć, koniec indeksu górnego, zamknięcie nawiasu, plus, nawias, dwa tysiące trzynaście indeks górny, pięć, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, siedem, koniec indeksu górnego, zamknięcie nawiasu., 3. Dwa ostatnie składniki mają wspólny czynnik w postaci dwa tysiące trzynaście indeks górny, cztery, koniec indeksu górnego, który możemy wyłączyć przed nawias otrzymując
nawias, jeden, plus, dwa tysiące trzynaście indeks górny, dwa, koniec indeksu górnego, zamknięcie nawiasu, razy, nawias kwadratowy, nawias, jeden, plus, dwa tysiące trzynaście, zamknięcie nawiasu, plus, dwa tysiące trzynaście indeks górny, cztery, koniec indeksu górnego, razy, nawias, jeden, plus, dwa tysiące trzynaście, zamknięcie nawiasu, zamknięcie nawiasu kwadratowego., 4. Z drugiej, trzeciej i czwartej pary możemy wyłączyć wspólne czynniki przez nawias:
nawias, jeden, plus, dwa tysiące trzynaście indeks górny, dwa, koniec indeksu górnego, zamknięcie nawiasu, plus, dwa tysiące trzynaście, razy, nawias, jeden, plus, dwa tysiące trzynaście indeks górny, dwa, koniec indeksu górnego, zamknięcie nawiasu, plus, dwa tysiące trzynaście indeks górny, cztery, koniec indeksu górnego, razy, nawias, jeden, plus, dwa tysiące trzynaście indeks górny, dwa, koniec indeksu górnego, zamknięcie nawiasu, plus, dwa tysiące trzynaście indeks górny, pięć, koniec indeksu górnego, razy, nawias, jeden, plus, dwa tysiące trzynaście indeks górny, dwa, koniec indeksu górnego, zamknięcie nawiasu., 5. Jeszcze raz możemy wyłączyć przed nawias wspólny czynnik
nawias, jeden, plus, dwa tysiące trzynaście indeks górny, dwa, koniec indeksu górnego, zamknięcie nawiasu, nawias, jeden, plus, dwa tysiące trzynaście, zamknięcie nawiasu, nawias, jeden, plus, dwa tysiące trzynaście indeks górny, cztery, koniec indeksu górnego, zamknięcie nawiasu., 6. Powyższe wyrażenie przekształca się do postaci
dwa tysiące czternaście, razy, nawias, jeden, plus, dwa tysiące trzynaście indeks górny, dwa, koniec indeksu górnego, zamknięcie nawiasu, nawias, jeden, plus, dwa tysiące trzynaście indeks górny, cztery, koniec indeksu górnego, zamknięcie nawiasu., 7. Przekształcimy wyrażenie: jeden, plus, dwa tysiące trzynaście, plus, dwa tysiące trzynaście indeks górny, dwa, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, trzy, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, cztery, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, pięć, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, sześć, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, siedem, koniec indeksu górnego., 8. Zaczniemy od zamiany kolejności składników w rozważanej sumie:
jeden, plus, dwa tysiące trzynaście indeks górny, dwa, koniec indeksu górnego, plus, dwa tysiące trzynaście, plus, dwa tysiące trzynaście indeks górny, trzy, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, cztery, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, sześć, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, pięć, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, siedem, koniec indeksu górnego., 9. Ponieważ każdy z czynników powyższego iloczynu jest liczbą naturalną, więc rozważana liczba jest podzielna przez nawias, jeden, plus, dwa tysiące trzynaście indeks górny, dwa, koniec indeksu górnego, zamknięcie nawiasu, nawias, jeden, plus, dwa tysiące trzynaście indeks górny, cztery, koniec indeksu górnego, zamknięcie nawiasu., 10. Ponownie możemy wyłączyć przed nawias wspólny czynnik:
nawias, jeden, plus, dwa tysiące trzynaście indeks górny, dwa, koniec indeksu górnego, zamknięcie nawiasu, nawias, jeden, plus, dwa tysiące trzynaście, plus, dwa tysiące trzynaście indeks górny, cztery, koniec indeksu górnego, plus, dwa tysiące trzynaście indeks górny, pięć, koniec indeksu górnego, zamknięcie nawiasu.

Ćwiczenie 10

Udowodnij, że liczba $(n^{2} - 4) (n^{3} - n)$ jest podzielne przez $5$ dla dowolnej liczby całkowitej $n$ .

Skorzystaj ze wzoru: $a^{2} - b^{2} = (a - b) (a + b)$ .

Wyłączmy $n$ przed drugi nawias $(n^{2} - 4) (n^{3} - n) = (n^{2} - 4) \cdot n \cdot (n^{2} - 1)$ .

Korzystając ze wzoru $a^{2} - b^{2} = (a - b) (a + b)$ możemy każdy z nawiasów przedstawić jako iloczyn:

$(n - 2) (n + 2) \cdot n \cdot (n - 1) (n + 1) = (n - 2) (n - 1) \cdot n \cdot (n + 1) (n + 2)$

Zauważmy, ze liczby $n - 2$ , $n - 1$ , $n$ , $n + 1$ , $n + 2$ to pięć kolejnych liczb całkowitych, więc dokładnie jedna z nich dzieli się przez przez $5$ .

Iloczyn liczby podzielnej przez $5$ i liczby całkowitej jest podzielny przez $5$ .

Słownik

Diofantos

grecki matematyk żyjący w Aleksandrii w III w n.e; znany głównie ze swojego dzieła w $13$ księgach zwanego Arytmetyka, w którym opisuje zagadnienia związane z rozwiązywaniem równań

równanie diofantyczne

równanie, którego rozwiązań szukamy w zbiorze liczb całkowitych (lub jego podzbiorach)

silnia

działanie jednoargumentowe, które liczbie naturalnej dodatniej przyporządkowuje iloczyn wszystkich liczb naturalnych dodatnich niewiększych od danej liczby, ponadto liczbie zero przyporządkowuje liczbę $1$ ; silnię oznaczamy wykrzyknikiem: $n!$ ; czytamy “ $n$ silnia”; zatem $0! = 1$ , $1! = 1$ , $n! = 1 \cdot 2 \cdot 3 \cdot . . . \cdot n$ dla liczb naturalnych $n$ większych od $1$

7. NWD, NWW

9*. Liczby pierwsze - zastosowania, ciekawostki (DODATEK)

8. Dowody dotyczące podzielności liczb całkowitych

Słownik