Elementarna teoria liczb - ebook

PRZEDMOWA DO WYDANIA DRUGIEGO

W czasie ponad piętnastu lat używania podręcznika otrzymaliśmy sporo uwag na jego temat. Najczęściej pojawiającym się postulatem było dopisanie odpowiedzi do ćwiczeń i zadań z podręcznika. Poszliśmy za głosem czytelników, zamieszczając odpowiedzi i podpowiedzi (wskazówki) do wielu ćwiczeń i zadań. Część rozwiązań znajduje się w „Teorii liczb z programem Mathematica”, nowej książce Wydawnictwa PWN. Do książki tej wybrano ćwiczenia i zadania, które nadają się do eksperymentów.

W drugim wydaniu dodaliśmy kilka wątków, np. błyskotliwy dowód poprawności testu Lucasa-Lehmera, oraz kilka aktualizacji (np. tablicę największych znanych liczb pierwszych).

Uważamy, że naszą powinnością jest przypomnienie podziękowań wyrażonych we wstępie do pierwszego wydania „Elementarnej teorii liczb”. Chcemy raz jeszcze podkreślić rolę Jerzego Browkina, Adama Mysiora, Jerzego Rutkowskiego oraz Jerzego Urbanowicza w nadaniu temu podręcznikowi jego ostatecznej formy. Niestety wszyscy oni już dzisiaj nie żyją. W tym miejscu wypada także zaznaczyć istotną rolę Stanisława Wawrykiewicza, autora składu TEX pierwszego wydania, w nadaniu formy graficznej książki. Nieszczęśliwym zbiegiem losu i on już nie żyje od kilku lat.

Chcielibyśmy bardzo podziękować Panom Dominikowi Burkowi, Krzysztofowi Kowitzowi, Adamowi Nawrockiemu i Maciejowi Radziejowskiemu za sugestie dotyczące rozwiązań niektórych zadań.

Jesteśmy ogromnie wdzięczni Wydawnictwu PWN – Panu Karolowi Zawadzkiemu za inicjatywę wydania tej książki i „Teorii liczb z programem Mathematica” oraz Pani Małgorzacie Kopczyńskiej za bardzo uważną redakcję i korekty. Panu Lechowi Chańko dziękujemy za piękny skład i wielką cierpliwość.

Trójmiasto – Poznań

wrzesień 2021

AutorzyWSTĘP

Niniejszy podręcznik zawiera opracowany materiał prowadzonych przez nas od wielu lat wykładów i ćwiczeń z teorii liczb dla studentów matematyki i informatyki. Teoria liczb, jedna z dwóch (obok geometrii) najstarszych dziedzin matematyki, to ogromny, budowany od ponad dwóch tysięcy lat dział matematyki, pełen pięknych rezultatów i różnorodnych metod. W pełni podzielamy opinię wybitnego angielskiego matematyka Hardy'ego, który apelował, aby właśnie teoria liczb pojawiała się jak najwcześniej w edukacji matematycznej ze względu na prostotę jej pojęć i rozumowań. Oczywiście na przestrzeni wieków w teorii liczb pojawiło się wiele skomplikowanych metod i technik oraz bardzo trudnych twierdzeń. Niektóre takie twierdzenia przytaczamy w podręczniku, podając źródła z dokładniejszym ich omówieniem.

Przymiotnik „elementarna” w tytule książki dobrze oddaje dobór treści, nasz podręcznik bowiem opisuje najprostsze pojęcia i fakty teorii liczb (zakres przedstawionego materiału jest oczywiście naszym subiektywnym wyborem). Chcielibyśmy, aby opracowanie służyło zarówno studentom, jak i nauczycielom akademickim prowadzącym wykłady i ćwiczenia z teorii liczb. Mamy też nadzieję, że zafascynowani pięknem teorii liczb, sięgną po ten podręcznik także uczniowie szkół średnich i nauczyciele prowadzący kółka matematyczne.

Dla podkreślenia przeznaczenia tej książki – podręcznika towarzyszącego 30-godzinnemu wykładowi – zachowano podział materiału na 15 dwugodzinnych wykładów. Ponadto materiał został przedstawiony w działach tematycznych, na końcu każdego działu zamieszczono ćwiczenia, których rozwiązanie pozwoli Czytelnikowi lepiej zrozumieć omówiony wcześniej materiał i nabrać większej wprawy w stosowaniu poznanych algorytmów. Oprócz tego na zakończenie kilku działów podane zostały zadania, na ogół trudniejsze od ćwiczeń; niektóre z tych zadań pokazują inne fakty związane z omawianymi zagadnieniami.

Do korzystania z podręcznika wystarczy znajomość elementów teorii mnogości, algebry i analizy matematycznej w zakresie pierwszych dwóch lat typowych kursów uniwersyteckich z tych przedmiotów. Warto podkreślić, że teoria liczb jest wspaniałym źródłem tematów do pisania własnych programów komputerowych, dzięki którym łatwiej badać jej problemy; można też wykorzystać matematyczne pakiety typu MATHEMATICA, MAPLE czy DERIVE, które zawierają bogate biblioteki z programami z teorii liczb.

Podręcznik powstał dzięki życzliwości wielu osób. Dziękujemy doktorowi Jerzemu Rutkowskiemu (recenzentowi skryptowej wersji podręcznika), którego wnikliwe i szczegółowe uwagi pozwoliły uniknąć wielu usterek. Chcielibyśmy także wspomnieć nieżyjącego już doktora Adama Mysiora, który przeczytał maszynopis, wprowadzając do niego wiele zmian i poprawek. Serdecznie dziękujemy też profesorom Jerzemu Browkinowi i Jerzemu Urbanowiczowi, uwzględnienie ich recenzji i wprowadzenie dalszych zmian stworzyło ostateczną postać naszego podręcznika.

Poznań – Gdańsk

marzec – kwiecień 2006

AutorzyWYKŁAD 1

1. Liczby naturalne i całkowite

Pełny obraz aksjomatyki zbioru liczb naturalnych i podstawowe własności zbioru liczb całkowitych Czytelnik może znaleźć na przykład w . Przypomnimy podstawowe fakty dotyczące zbioru liczb naturalnych.

Aksjomat indukcji

Jeśli jest dowolnym zbiorem takim, że

(1)

(2) dla dowolnego , jeśli , to ,

to .

Konsekwencjami aksjomatu indukcji są:

Twierdzenie 1.1 (zasada maksimum)

W każdym niepustym ograniczonym podzbiorze zbioru liczb naturalnych istnieje element największy.

Twierdzenie 1.2 (zasada minimum)

W każdym niepustym podzbiorze zbioru liczb naturalnych istnieje element najmniejszy.

Twierdzenie 1.3 (zasada indukcji matematycznej zupełnej)

Niech każdej liczbie naturalnej przyporządkowane będzie zdanie logiczne . Wówczas z założeń:

(1) zdanie jest prawdziwe,

(2) dla każdego , jeśli zdanie jest prawdziwe, to zdanie jest prawdziwe,

wynika prawdziwość zdań dla każdego .

Ćwiczenia

1.

Udowodnij, że aksjomat indukcji i twierdzenia 1.1, 1.2 oraz 1.3 są równoważne.

2.

Znajdź błąd w dowodzie następującego „twierdzenia”: Wszystkie koty są jednakowego koloru.

Dowód

Wystarczy pokazać, że spełniony jest następujący warunek: Dla każdego w dowolnym zbiorze złożonym z kotów wszystkie koty są jednakowego koloru. Dla warunek oczywiście zachodzi. Załóżmy, że warunek zachodzi dla . Pokażemy, że zachodzi dla . W zbiorze złożonym z kotów, zgodnie z założeniem indukcyjnym, kotów ma ten sam kolor, na przykład czarny:

Ale z założenia indukcyjnego koty są też jednakowego koloru. Ponieważ koty są czarne, więc kot jest też czarny.

3.

Wykaż, że dla każdego liczba jest wielokrotnością liczby 13.

4.

Niech , . Przez oznaczamy liczbę . Sprawdź, że .

5.

Niech , . Sprawdź, że .

6.

Wykaż, że dla każdego zachodzi następująca równość:

.

7.

Dla oznaczmy przez sumę . Sprawdź, że dla każdych :

.

8.

Wyprowadź wzory na , , , . Udowodnij ich prawdziwość, stosując metodę indukcji matematycznej.

9.

Udowodnij, że maksymalna liczba jednomianów (które nie są podobne) wielomianu zmiennych stopnia jest równa .