Teoria liczb z programem Mathematica - ebook

WSTĘP

W 2006 roku w Wydawnictwie Naukowym PWN został wydany podręcznik „Elementarna teoria liczb” . 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 , znajdziemy w niej definicje, twierdzenia (bez dowodów) z 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 . 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 Zarzycki1. PODZIELNOŚĆ I ALGORYTM EUKLIDESA

1.1. Podzielność

W zbiorze liczb całkowitych 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 .

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 oraz , , istnieją jednoznacznie określone liczby całkowite , takie, że , gdzie . Liczbę nazywamy ilorazem, liczbę resztą. W szkole mówi się, że liczba całkowita jest podzielna przez różną od zera liczbę całkowitą , jeśli reszta z dzielenia przez wynosi zero. Definicja „akademicka” jest taka: Liczba całkowita jest PODZIELNA przez liczbę całkowitą , jeśli istnieje taka liczba całkowita , że . Liczbę nazywamy DZIELNIKIEM liczby , o liczbie mówi się, że jest WIELOKROTNOŚCIĄ liczby . Podzielność przez oznaczamy .

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

Oto kilka przykładów:

In := Mod

Out = 0

In := Quotient

Out = 15

In := QuotientRemainder

Out = 15, 0

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

In := Divisible , Out = True

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

TableForm , Range ], TableHeadings→Automatic]

w której poszczególne polecenia oznaczają:

• TableForm – wyniki przedstawione w postaci tabelki,

• Outer – do każdej pary z zakresu (Range ) znajdujemy resztę dzielenia przez (funkcja Mod),

• TableHeadings→Automatic oznacza nagłówki, w tym przypadku zakres .

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 ( , ćw. 3a, s. 6)

Wykaż, że dla każdego zachodzi podzielność . W typowym rozwiązaniu wykorzystuje się zasadę indukcji matematycznej. My jednak zaczniemy od sprawdzenia własności dla ; wykorzystamy komendę Table, która tablicuje wartości funkcji:

Table , {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 }, {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 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 przez 8 dla 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!

Zadanie 1.1.2

Wymyśl swoje zadanie na podzielność, tzn. znajdź taką formę zdaniową ze zmienną , która jest prawdziwa dla każdej liczby naturalnej . 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 ? 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

39960476719­7679837599445­500494892677304­312411393­504462­234085050711176­5583510003404­87308292150­13285575574050084­5026354958566­842349308­52964049255­01147904­980525543924051417­41467622663380­996415300301627604636­83228716493161641­849577060992­5454005241358460­3115238875395834378096­40729544084416875015693643­78521346068696151408976826­8527740198439718­7058217295565624­9821044933455946­728971684122744367­03671643480698487769­322205969116119200988786­32447745738858068163211­4549526418546285658051­09986803145743­950677763724117673700­658910538966372910576497­65297775399933441028357­5693174950­5800511657958­3423074295515476­64340412251297383­0834900613508158232­9601233419­8550933284553542­8593260370501569­211503336504742­906632218389869­139417713982987­43832817061510204420­2004965177426389783­09820412833593072­90811317959191610­4281423410­5611631363844429­2161521869499742308­7899869990980304­18294836728874­2459397024108­9519266416799764385­6404681020362660758917­37546562502630401­5195283527

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 jest podzielna przez 3… (o znowu trzy kropki!). A teraz liczba cyfr rozpatrywanej liczby: zauważmy, że największy „wkład” ma składnik , znajdźmy ilość cyfr tej liczby. Nietrudno zauważyć, że ilość cyfr liczby naturalnej można obliczyć za pomocą wzoru +1$], gdzie $] oznacza część całkowitą liczby . Zatem powinniśmy obliczyć +1$], ta liczba ma wartość 952 (Floor ] + 1). Na koniec należy się zastanowić, jak podzielenie liczby przez 6 wpłynie na liczbę cyfr. Przydałaby się informacja o pierwszej cyfrze liczby . W tym celu należałoby znaleźć takie ( , aby spełniona była podwójna nierówność . Obliczenia numeryczne dają odpowiedź: . Wynika stąd, że dzieląc przez 6, liczba cyfr zmniejsza się o 1. Stąd ostatecznie rozpatrywana liczba ma rzeczywiście 951 cyfr .

Zadanie 1.1.4 ( , ćw. 17, s. 7)

Wykaż, że iloczyn kolejnych liczb całkowitych jest podzielny przez . Jeśli w zestawie 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 ; chcemy pokazać, że

.

Poeksperymentujmy najpierw numerycznie :

f := Product

To jest definicja iloczynu ; zwracamy uwagę na oznaczenie zmiennych, koniecznie należy używać dolnego podkreślnika.

f /5! wynik 56

f /10! wynik 19448

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

,

gdzie oznacza symbol Newtona . 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 ( , ćw. 18, s. 7)

Udowodnij, że dla dowolnego , liczba nie jest podzielna przez . Podobnie, jak w zadaniu 1.1.1, kluczową rolę odgrywa podzielność przez 8; sprawdźmy to:

Table , {n,2,20}]

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

Table ,{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 dla każdego , to wystarczy sprawdzić, że 8 nie jest dzielnikiem liczby . 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 przez liczby ;

b) liczb postaci przez liczby ;

c) liczb postaci przez liczby , – ustalona liczba naturalna;

d) liczb postaci przez liczby .

Krzysztof Kowitz zauważył, że nie dzieli dla żadnych liczb parzystych oraz dla , gdzie . Biorąc moduł 16, np. dla otrzymujemy:

Table , {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 , wynika, że nie dzieli . Pozostaje sprawdzić, że nie dzieli dla żadnej liczby całkowitej dodatniej . Tutaj można skorzystać z pomocy programu Mathematica; za pomocą komendy

Table, {i,0,2^14–1}]

można zauważyć, że ciąg reszt liczb postaci modulo jest okresowy, nie występuje w nim liczba 0 i jego okres wynosi .

Zadanie 1.1.7 ( , zad. 6, s. 13)

Udowodnij, że dla każdej liczby naturalnej i dla każdej liczby naturalnej nieparzystej liczba jest dzielnikiem liczby . 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 ).

Sum = 1/2n(1 + n)

Sum = 1/4 n^2 (1 + n)^2

Sum = 1/12 n^2 (1 + n)^2 (–1 + 2 n + 2n^2)

Dla podzielność jest oczywista, dla także, natomiast dla należy wykazać, że 6 jest dzielnikiem liczby dla dowolnej liczby naturalnej . Jasne jest, że 2 dzieli jedną z liczb , , natomiast 3 dzieli jedną z liczb , , , co sprawdza się, rozpatrując trzy przypadki, w zależności od reszty z dzielenia przez 3.

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

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

.

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

Factor

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

Factor

(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 jest nieparzyste):

(*) .

Omówimy dokładniej przypadek, gdy jest liczbą parzystą. Wówczas:

Z (*) mamy wtedy:

oraz

.

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