Projekt okładki: Ireneusz Gawliński

Wydawca: Karol Zawadzki

Koordynator ds. redakcji: Adam Kowalski

Redaktor: Małgorzata Kopczyńska

Produkcja: Mariola Grzywacka

Książka, którą nabyłeś, jest dziełem twórcy i wydawcy. Prosimy, abyś przestrzegał praw, jakie im przysługują. Jej zawartość możesz udostępnić nieodpłatnie osobom bliskim lub osobiście znanym. Ale nie publikuj jej w Internecie. Jeśli cytujesz jej fragmenty, nie zmieniaj ich treści i koniecznie zaznacz, czyje to dzieło. A kopiując jej część, rób to jedynie na użytek osobisty.

Szanujmy cudzą własność i prawo.

Więcej na www.legalnakultura.pl

Polska Izba Książki

Copyright © by Wydawnictwo Naukowe PWN SA

Warszawa 2022

ISBN: 978-83-01-22166-9

DOI: https://doi.org/10.53271/2022.001

eBook został przygotowany na podstawie wydania papierowego z 2022 r. (wyd. I)

Warszawa 2022

Wydawnictwo Naukowe PWN SA

infolinia 801 33 33 88

tel. 22 69 54 321; faks 22 69 54 288

e-mail: pwn@pwn.com.pl; www.pwn.pl

Skład wersji elektronicznej na zlecenie Wydawnictwa Naukowego PWN SA: mobisfera.pl

Wstęp

 W 2006 roku w Wydawnictwie Naukowym PWN został wydany podręcznik „Elementarna teoria liczb”  [ETL1]. Książka ta okazała się przydatna we wprowadzaniu podstawowych pojęć i twierdzeń teorii liczb zarówno na poziomie szkolnym, jak i na poziomie akademickim. Wielokrotnie prowadziłem zajęcia, korzystając z niej. W czasie tych zajęć starałem się wpleść wątki technologiczne, używając przede wszystkim programu Mathematica. Program ten, bez wątpienia gwiazda wśród programów tego typu, jest przyjazny dla użytkownika i nawet osoby nieznające zbyt dobrze tego programu mogą z jego pomocą rozwiązywać trudne zadania z teorii liczb.

 Niniejszą książkę można więc uważać do pewnego stopnia za suplement do  [ETL2], znajdziemy w niej definicje, twierdzenia (bez dowodów) z  [ETL2] ilustrowane „technologicznie” i przede wszystkim zadania, przy rozwiązaniu których korzysta się z programu Mathematica. Metoda rozwiązywania takich zadań polecana w tej książce to eksperymenty. W prezentowanych rozwiązaniach zadań niekiedy nie stawiam kropki nad i – nie podaję ich pełnych rozwiązań, uważam bowiem, że zamieszczone opisy eksperymentów stanowią znaczącą podpowiedź do teoretycznych rozważań. Technologiczne wspomaganie nauczania i uczenia się matematyki niesie w sobie pewne niebezpieczeństwo, studenci, a zwłaszcza uczniowie często myślą, że sprawdzenie wielu przypadków jest rozwiązaniem. Tak jest, ale tylko wtedy, gdy mamy pewność, że zbiór potencjalnych rozwiązań, np. jakiegoś równania, jest skończony. Najczęściej eksperymenty numeryczne to początek drogi i należy to uzmysławiać wszystkim, którzy używają programów typu Mathematica . W książce pojawiają się definicje i twierdzenia, ale poza komentarzami i eksperymentami numerycznymi nie ma dowodów tych twierdzeń, gdyż bardzo wiele z nich znajduje się w podręczniku  [ETL2]. Poza tym zdecydowana większość twierdzeń z tej książki to klasyka teorii liczb. Ich dowody można znaleźć praktycznie w każdym podręczniku z tej dziedziny matematyki.

Zachęcam do eksperymentów numerycznych, komendy i procedury Mathematica są dość intuicyjne, ich poznawanie powinno być podporządkowane potrzebom związanym ze zrozumieniem pojawiających się twierdzeń i rozwiązywanych zadań. Podręcznik nie służy do nauki programu Mathematica. Mam nadzieję, że czytelnik odczuje radość, podobną do mojej w czasie pisania tej książki, gdy okazywało się, że przeprowadzane eksperymenty pozwoliły mi odkryć na nowo, zrozumieć wiele zagadnień teorii liczb.

Chciałbym wyrazić wdzięczność Panu Krzysztofowi Kowitzowi za uważne przeczytanie manuskryptu i szereg cennych uwag na temat jego zawartości.

Piotr Zarzycki

1. Podzielność i algorytm Euklidesa

1.1. Podzielność

W zbiorze liczb całkowitych dz$\Z = \{\ldots,-2,-1,0, 1, 2, \ldots\}$ określona jest relacja podzielności, a ponieważ znak liczby nie wpływa na podzielność, więc często, rozpatrując własności tej relacji, ograniczać się będziemy do zbioru liczb naturalnych dz$\N = \{1, 2, \ldots\}$.

Dzielenie liczb całkowitych, pojęcia podzielności, dzielnika, wielokrotności pojawiają się już w szkole podstawowej. Zasada dzielenia z resztą opiera się na następującym twierdzeniu:

Twierdzenie o dzieleniu z resztą

Dla dowolnych liczb całkowitych $a$ oraz $b$, $b \neq 0$, istnieją jednoznacznie określone liczby całkowite $q$, $r$ takie, że $a = qb + r$, gdzie $0\xleq r<\vert b\vert$. Liczbę $q$ nazywamy ilorazem, liczbę $r$ resztą. W szkole mówi się, że liczba całkowita $a$ jest podzielna przez różną od zera liczbę całkowitą $b$, jeśli reszta z dzielenia $a$ przez $b$ wynosi zero. Definicja „akademicka” [1] jest taka: Liczba całkowita $b$ jest podzielna przez liczbę całkowitą $a$, jeśli istnieje taka liczba całkowita $c$, że $b = a \cdot c$. Liczbę $a$ nazywamy dzielnikiem liczby $b$, o liczbie $b$ mówi się, że jest wielokrotnością liczby $a$. Podzielność $b$ przez $a$ oznaczamy $a\vert b$.

Popatrzmy teraz, jak z podzielnością radzi sobie Mathematica. Do sprawdzania, czy liczba $a$ jest podzielna przez liczbę $b$ , używamy komendy Mod  [a,b] (po wpisaniu tej komendy i naciśnięciu Shift + Enter otrzymujemy resztę z dzielenia $a$ przez $b$ ), do znalezienia ilorazu tego dzielenia służy komenda Quotient  [a,b]. Iloraz oraz resztę zwraca komenda QuotientReminder  [a,b].

Oto kilka przykładów:

 In [1] := Mod [45,3]

 Out [1] = 0

 In [2] := Quotient [45,3]

 Out [2] = 15

 In [3] := QuotientRemainder [45,3]

 Out [3] = 15, 0

Inny sposób sprawdzenia podzielności to Divisible  [a, b ], komenda, która zwraca prawdę albo fałsz w zależności od tego, czy liczba $a$ jest podzielna przez $b$,

  In [4] := Divisible [45, 3], Out [4]= True

Zanim przejdziemy do rozwiązywania zadań, popatrzmy na podzielność zilustrowaną za pomocą tabelki – komenda:

  TableForm [Outer [Mod, Range [8], Range [8]], TableHeadings→Automatic]

w której poszczególne polecenia oznaczają:

• TableForm – wyniki przedstawione w postaci tabelki,

• Outer – do każdej pary $(a,b)$ z zakresu $\{ 1, 2, 3, 4, 5, 6, 7, 8\}$  (Range [8]) znajdujemy resztę dzielenia $a$ przez $b$ (funkcja Mod),

• TableHeadings→Automatic oznacza nagłówki, w tym przypadku zakres $\{ 1, 2, 3, 4, 5, 6, 7, 8\}$.

Po tym wstępie teoretycznym rozwiążemy siedem zdań, we wszystkich poza zadaniem 1.1.2 wykorzystamy eksperymenty z programem Mathematica i podamy daleko idące wskazówki do pełnego rozwiązania; zadanie 1.1.2 polega na wymyśleniu własnych zadań dotyczących podzielności, Mathematica bardzo w tym pomaga.

Zadanie 1.1.1  ( [ETL2], ćw. 3a, s. 6)

Wykaż, że dla każdego $n\in \N$$n\in \N$ zachodzi podzielność $8\vert 5^{n}+2\cdot 3^{n-1}+1$. W typowym rozwiązaniu wykorzystuje się zasadę indukcji matematycznej. My jednak zaczniemy od sprawdzenia własności dla $n=1, 2, \ldots, 20$; wykorzystamy komendę Table, która tablicuje wartości funkcji:

 Table [Mod [5^n + 2*3^(n–1) + 1,8], {n,20}]

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

Odetchnęliśmy z ulgą, z dużą pewnością zajmujemy się prawdziwą własnością. Spójrzmy na kolejne podejście:

 Table [{Mod [5^n, 8], Mod [2*3^(n–1), 8]}, {n, 20}]

{{5,2}, {1,6}, {5,2}, {1,6}, {5,2}, {1,6}, {5,2}, {1,6}, {5,2}, {1,6}, {5,2}, {1,6}, {5,2}, {1,6}, {5,2}, {1,6}, {5,2}, {1,6}, {5,2}, {1,6}}

W każdym nawiasie otrzymaliśmy dwie reszty, które się powtarzają. Dla nieparzystych $n$ pierwsza jest równa 5, dla parzystych 1, natomiast druga reszta jest równa odpowiednio 2 lub 6. Suma zawsze wynosi 7. Dodając 1, otrzymujemy 8, czyli liczbę podzielną przez 8.

Pozostaje teraz podanie pełnego uzasadnienia, które opiera się na wykazaniu dwóch równości:

Spójrzmy, jak dowodzi się np. własności: reszta z dzielenia liczby $5^{n}$ przez 8 dla $n$ parzystego jest równa 1:

Być może niecierpliwy czytelnik zaprotestuje, pytając o ciąg dalszy. Nie będzie ciągu dalszego, odrobina wysiłku i pełny dowód będzie gotowy! [2]

Zadanie 1.1.2

Wymyśl swoje zadanie na podzielność, tzn. znajdź taką formę zdaniową ze zmienną $n$, która jest prawdziwa dla każdej liczby naturalnej $n$. Forma zdaniowa powinna być związana z podzielnością. Do znalezienia takiej formy zdaniowej bardzo przydają się eksperymenty z programem Mathematica!

Zadanie 1.1.3 (zadanie z konferencji Stowarzyszenia Nauczycieli Matematyki,1994)

Ile cyfr ma liczba $(1^{1992}+2^{1993}+3^{1994})/6$? W sformułowaniu jest zawarta sugestia, że rozpatrywana liczba jest całkowita. Jeden z uczestników zaskoczył wszystkich, podając rozwiązanie „maszynowe”, użył programu DERIVE, w którym obliczył daną liczbę i policzył jej cyfry. Zróbmy podobnie, używając Mathematica:

(1^1992 + 2^1993 + 3^1994)/6

399604767197679837599445500494892677304312411393504462234085050711176558351000340487308292150132855755740500845026354958566842349308529640492550114790498052554392405141741467622663380996415300301627604636832287164931616418495770609925454005241358460311523887539583437809640729544084416875015693643785213460686961514089768268527740198439718705821729556562498210449334559467289716841227443670367164348069848776932220596911611920098878632447745738858068163211454952641854628565805109986803145743950677763724117673700658910538966372910576497652977753999334410283575693174950580051165795834230742955154766434041225129738308349006135081582329601233419855093328455354285932603705015692115033365047429066322183898691394177139829874383281706151020442020049651774263897830982041283359307290811317959191610428142341056116313638444292161521869499742308789986999098030418294836728874245939702410895192664167997643856404681020362660758917375465625026304015195283527

 IntegerLength [%] = 951

Spróbujmy teraz rozwiązać to zadanie tradycyjnie; najpierw zajmiemy się „całkowitością” rozpatrywanej liczby: licznik jest parzysty, a jego ostatni składnik jest podzielny przez 3; ponadto liczba $1^{1992}+2^{1993}$ jest podzielna przez 3… (o znowu trzy kropki!). A teraz liczba cyfr rozpatrywanej liczby: zauważmy, że największy „wkład” ma składnik $3^{1994}$, znajdźmy ilość cyfr tej liczby. Nietrudno zauważyć, że ilość cyfr liczby naturalnej $k$ można obliczyć za pomocą wzoru $ [\log_{10}k]+1$, gdzie $ [x]$ oznacza część całkowitą liczby $x$. Zatem powinniśmy obliczyć $ [\log_{10}3^{1994}]+1$, ta liczba ma wartość 952  (Floor [Log [10, 3^1994]] + 1). Na koniec należy się zastanowić, jak podzielenie liczby $3^{1994}$ przez 6 wpłynie na liczbę cyfr. Przydałaby się informacja o pierwszej cyfrze liczby $3^{1994}$. W tym celu należałoby znaleźć takie $k$ ( $k=1, 2, \ldots, 9)$, aby spełniona była podwójna nierówność $k\cdot 10^{951}\xleq3^{1994}<(k+1)\cdot 10^{951}$. Obliczenia numeryczne dają odpowiedź: $k=2$. Wynika stąd, że dzieląc $3^{1994}$ przez 6, liczba cyfr zmniejsza się o 1. Stąd ostatecznie rozpatrywana liczba ma rzeczywiście 951 cyfr [3].

Zadanie 1.1.4  ( [ETL2], ćw. 17, s. 7)

Wykaż, że iloczyn $k$ kolejnych liczb całkowitych jest podzielny przez $k!$. Jeśli w zestawie $k$ kolejnych liczb całkowitych znajduje się zero, to podzielność oczywiście zachodzi. Ponieważ znak liczby całkowitej nie wpływa na podzielność, więc możemy zakładać, że wszystkie liczby są dodatnie. Rozpatrujemy więc liczby naturalne $m+1, m+2, \ldots, m+k$; chcemy pokazać, że

$k!\vert (m+1)\cdot(m+2)\cdot \ldots\cdot (m+k)$.

Poeksperymentujmy najpierw numerycznie [4]:

  f [m_, k_] := Product [i, {i, m + 1, m + k}]

To jest definicja iloczynu $(m+1)\cdot (m+2)\cdot \ldots\cdot (m+k)$; zwracamy uwagę na oznaczenie zmiennych, koniecznie należy używać dolnego podkreślnika.

 f [3, 5]/5! wynik 56

 f [7,10]/10! wynik 19448

Uzasadnienie w przypadku ogólnym polega na zauważeniu, że

$\Frac{f(m,k)}{k!}={m+k\choose m}$,

gdzie ${m+k\choose m}$ oznacza symbol Newtona [5]. Wystarczy teraz powołać się na własność trójkąta Pascala, który składa się z liczb naturalnych (można to udowodnić, korzystając z indukcji matematycznej).

Zadanie 1.1.5  ( [ETL2], ćw. 18, s. 7)

Udowodnij, że dla dowolnego $n\in \N\setminus\{1\}$, liczba $3^n+1$ nie jest podzielna przez $2^n$. Podobnie, jak w zadaniu 1.1.1, kluczową rolę odgrywa podzielność przez 8; sprawdźmy to:

 Table [Mod [3^n + 1,8], {n,2,20}]

{2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2}

 Table [Mod [2^n, 8],{n,2,20}]

{4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

Skoro 8 jest dzielnikiem liczby $2^{n}$ dla każdego $n\xgeq3$, to wystarczy sprawdzić, że 8 nie jest dzielnikiem liczby $3^{n}+1$. Widać z powyższych danych, że

Jesteśmy pewni, że czytelnik poradzi sobie z uzasadnieniem własności z poprzedniej strony (można zerknąć do rozwiązania zadania 1.1.1).

Zadanie 1.1.6

Zbadaj podzielność:

a) liczb postaci $4^{n}+1$ przez liczby $3^{n}$;

b) liczb postaci $5^{n}+1$ przez liczby $4^{n}$;

c) liczb postaci ${(k+1)}^{n}+1$ przez liczby $k^{n}$, $k$ – ustalona liczba naturalna;

d) liczb postaci $3^{n}+n$ przez liczby $2^{n}$.

Krzysztof Kowitz zauważył, że $2^{n}$ nie dzieli $3^{n}+n$ dla żadnych liczb parzystych $n$ oraz dla $n=16k+r$, gdzie $r\in\{1, 3, 5, 7, 9, 11, 15\}$. Biorąc moduł 16, np. dla $n=16+5$ otrzymujemy:

Table  [Mod  [3^(16k + 5) + 16k + 5, 16], {k, 0, 20} ]

8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8

Z kongruencji $3^{16k+5}+16k+5\equiv 8\ (\mod\ 16)$, $2^{16k+5}\equiv 0\ (\mod\ 16)$ wynika, że $2^{16k+5}$ nie dzieli $3^{16k+5}+16k+5$. Pozostaje sprawdzić, że $2^{16k+13}$ nie dzieli $3^{16k+13}+16k+13$ dla żadnej liczby całkowitej dodatniej $k$. Tutaj można skorzystać z pomocy programu Mathematica; za pomocą komendy

Table[Mod[3^(16*i+13)+16*i+13, 2^14], {i,0,2^14–1}]

można zauważyć, że ciąg reszt liczb postaci $3^{16n+13}+16n+13$ modulo $2^{14}$ jest okresowy, nie występuje w nim liczba 0 i jego okres wynosi $2^{14}$.

Zadanie 1.1.7  ( [ETL2], zad. 6, s. 13)

Udowodnij, że dla każdej liczby naturalnej $n$ i dla każdej liczby naturalnej nieparzystej $k$ liczba $1+2+\ldots+n$ jest dzielnikiem liczby $1^{k}+2^{k}+\ldots+n^{k}$. Do rozwiązania tego zadania wykorzystamy kilka wzorów, które możemy otrzymać, wywołując je z pamięci programu Mathematica (obok zdefiniowanej w programie sumy zamieściliśmy także wzór jawny dla $k=1, 3, 5$).

 Sum [i, {i,1,n}] = 1/2n(1 + n)

 Sum [i^3, {i,1,n}] = 1/4 n^2 (1 + n)^2

 Sum [i^5, {i,1,n}] = 1/12 n^2 (1 + n)^2 (–1 + 2 n + 2n^2)

Dla $k=1$ podzielność jest oczywista, dla $k= 3$ także, natomiast dla $k= 5$ należy wykazać, że 6 jest dzielnikiem liczby $n(n+1)(2n^{2}+2n-1)$ dla dowolnej liczby naturalnej $n$. Jasne jest, że 2 dzieli jedną z liczb $n$, $n+1$, natomiast 3 dzieli jedną z liczb $n$, $n+1$, $2n^2+2n-1$, co sprawdza się, rozpatrując trzy przypadki, w zależności od reszty z dzielenia $n$ przez 3.

Dla trzech konkretnych wartości $k$ sprawdziliśmy podzielność dla dowolnego $n$. A jak będzie dla dowolnego nieparzystego $k$?

Rozpoczniemy od podzielności: dla dowolnej liczb naturalnej nieparzystej $k$ i dla dowolnych liczb całkowitych $a$, $b$ zachodzi podzielność:

$a+b\, \vert\, a^{k}+b^{k}$.

Spójrzmy na kilka rozkładów z programu Mathematica:

 Factor [a^5 + b^5]

(a+b) (a^4 – a^3 b + a^2 b^2 – a b^3 + b^4)

 Factor [a^7 + b^7]

(a+b) (a^6 – a^5 b + a^4 b^2 – a^3 b^3 + a^2 b^4 – a b^5 + b^6)

Pozwala to na zapisanie rozkładu w przypadku ogólnym (pamiętajmy, że $k$ jest nieparzyste):

(*) $a^{k}+b^{k}=(a+b)(a^{k-1}-a^{k-2}b+\ldots+b^{k-1})$.

Omówimy dokładniej przypadek, gdy $n=2m$ jest liczbą parzystą. Wówczas:

Z (*) mamy wtedy:

oraz

$m\,\vert\,(m-(m-1))^k+(m-(m-2))^k+\ldots+m^k+(m+1)^k+\ldots$ $+\,(m+(m-1))^k+(m+m)^k$.

Podobnie postępujemy, gdy $n$ jest liczbą nieparzystą.

Przypisy

 [1] Celowo rozróżniamy dwa rodzaje definicji, szkolną i akademicką.

 [2] Czy dużo będzie jeszcze? Tak, dość dużo.

 [3] W języku Mathematica do poszukiwania konkretnych cyfr liczby naturalnej przydają się komendy: IntegerDigits oraz FromDigits.

 [4] W języku Mathematica  funkcja f  [m, k] jest ściśle związana z funkcją Pochhammera (Pochhammer [ 1 + m, k]).

 [5]  Binomial [m, k] (Mathematica) oznacza symbol Newtona ${m\choose k}$.