Составители:
Рубрика:
3
Моей дочери Анастасии Ерош посвящаю
ВВЕДЕНИЕ
Одним из разделов дискретной математики является теория чисел,
которая первоначально изучала свойства целых чисел. Целое число яв-
ляется одним из древнейших математических понятий, связанных с
подсчетом окружающих предметов. Теория чисел возникла из задач
арифметики и первоначально оперировала четырьмя арифметическими
действиями над натуральными (целыми, положительными) числами.
Основными понятиями этой теории являлись простые числа, состав-
ные числа, квадратные числа (числа, равные квадрату некоторого
другого числа), совершенные числа (числа равные сумме своих дели-
телей). В VI веке до н.э. в Древней Греции было известно решение урав-
нения x
2
+ y
2
= z
2
в целых числах.
В III веке до н.э. Евклид в “Началах” обосновал алгоритм нахожде-
ния наибольшего общего делителя двух произвольных целых чисел и
доказал, что количество простых чисел является бесконечным. Эра-
тосфен предложил метод нахождения простых чисел (“Решето Эратос-
фена”). Систематизация проблем теории чисел и методов их решений
была выполнена в III веке н.э. Диофантом в “Арифметике”. В XVII
веке н.э. Ферма исследовал решения многих уравнений в целых числах
и высказал гипотезу, что уравнение x
n
+ y
n
= z
n
, n>2, x, y, z – целые, не
имеет решений (великая теорема Ферма). Ему также принадлежит ут-
верждение, что если a и p (p – простое число) взаимно простые числа
(наибольший общий делитель этих чисел равен 1), то a
p
– a делится на
p нацело (малая теорема Ферма). Эйлер доказал великую теорему Фер-
ма при n = 3 и обобщил малую теорему Ферма, введя понятие функции
ϕ(m) – количества чисел ряда 1, 2, 3, …, m взаимно простых с m, ныне
называемую функцией Эйлера от целого m, и показал, что любое число a
взаимно простое с m, возведенное в степень ϕ(m), при делении на m дает
в остатке 1. Проблема нахождения целых положительных остатков при
делении одного целого на другое возникла из задач календарных расче-
тов в Китае (Сунь-цзы, Цинь Цзюшао) и в современном виде формули-
руется как китайская теорема об остатках.
Важным понятием теории чисел являются сравнения, основные свой-
ства которых были доказаны Гауссом. Сравнение является свойством
эквивалентности чисел, имеющих одинаковые положительные остатки
при делении на некоторое целое число – модуль.
