Teoria liczb jest dziedziną matematyki, zajmującą się badaniem własności liczb – początkowo tylko naturalnych. Obecnie należałoby powiedzieć: głównie naturalnych. Jej początki sięgają starożytności. Zajmowali się nią Pitagoras, Euklides, Eratostenes, Diofantos i wielu innych. Bujny rozwój teorii liczb datuje się mniej więcej od czasów działalności Pierre'a Fermata (1601-1665), autora wypowiedzi słynnego Wielkiego Twierdzenia Fermata. Do dwudziestego wieku powszechną była opinia, iż teoria ta nie ma żadnego zastosowania. Jednak dzięki wielkiemu rozwojowi kryptografii - nauki zajmującej się układaniem i łamaniem szyfrów - pogląd ten musiał zostać zweryfikowany.
W dwu kolejnych wykładach poznamy podstawowe pojęcia i klasyczne twierdzenia teorii liczb - niektóre pochodzące jeszcze z czasów starożytnych. Zainteresowanych zachęcamy do rozszerzenia swej wiedzy w kursie Matematyka Dyskretna 2, gdzie przedstawiony jest system kryptograficzny RSA, oparty na tych podstawowych faktach z teorii liczb.
Uwaga
W wykładach poświęconych teorii liczb wszystkie liczby są całkowite, chyba że wyraźnie jest powiedziane inaczej.
Uwaga
W wykładach dotyczących teorii liczb poznamy też kilka algorytmów operujących na liczbach naturalnych. Rozważając ich złożoność musimy poczynić kilka założeń o złożoności podstawowych operacji arytmetycznych. Długość liczby \( n \) to liczba bitów \( n \), czyli liczba cyfr w zapisie binarnym (dwójkowym). Wynosi ona \( \lfloor \lg{n}\rfloor+1 \), ale nam wystarcza wiedzieć, że jest ona \( O(\lg{n}) \). Przyjmujemy, że złożoność dodawania liczb \( a \) i \( b \) jest proporcjonalna do sumy ich długości, dokładniej że jest \( O(\lg{a}+\lg{b}) \) oraz że złożoność mnożenia liczb \( a \) i \( b \) jest \( O(\lg{a}\lg{b}) \) (choć znane są szybsze algorytmy).