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 ⌊lgn⌋+1, ale nam wystarcza wiedzieć, że jest ona O(lgn). Przyjmujemy, że złożoność dodawania liczb a i b jest proporcjonalna do sumy ich długości, dokładniej że jest O(lga+lgb) oraz że złożoność mnożenia liczb a i b jest O(lgalgb) (choć znane są szybsze algorytmy).