Wykł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 [7]. 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 .

Wstę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

Autorzy