Часть математики, изучающая целые числа, называется арифметикой или теорией чисел. Это один из самых красивых разделов математики. Хотя школьники знакомятся с ним очень рано, он является довольно трудным. В арифметике имеется много задач, еще не решенных учеными, хотя их формулировку может понять даже первоклассник. О некоторых из них будет идти речь ниже.
Сначала опишем объекты, о которых пойдет речь.
1. Натуральные числа - это числа , , , ... Они возникают в процессе счета и означают количество предметов. Множество всех натуральных чисел обозначается через .
2. Целые числа - это числа ..., , , , , , , , ..., т.е. число , натуральные числа и числа, противоположные по знаку натуральным. Множество всех целых чисел обозначается через . Натуральные числа можно складывать и умножать. Вычитание натуральных чисел определяется как операция, обратная сложению. А именно, равенство означает, что . Это вычитание выполнимо не всегда, а лишь в том случае, когда . В множестве целых чисел вычитание натуральных чисел всегда выполнимо. А именно, надо положить , а если , то . Сложение любых целых чисел и их вычитание, а также умножение выполняются с помощью известных правил знаков.
3. Свойства арифметических операций хорошо известны. Они часто используются без специального упоминания о них. Всюду в дальнейшем буквы , , означают любые целые числа.
Если , то или
Следствие. Если , и , то , т.е. уравнение имеет не более одного решения в целых числах.
4. Делимость. Определение. Пусть , - целые числа. Говорят, что - делитель , или что делит , или что кратно ( - кратное ), или что делится на , если существует такое целое число , что . Записывают этот факт в виде: .
Упражнение. Докажите, что
если и , то и ;
если и - любое целое число, то .
Проследите, какие из правил, приведенных в п. 3, здесь применяются.
5. Деление с остатком. Определение. Пусть - целое, - натуральное число. Разделить с остатком на - значит найти такие целые числа и , что , где число таково, что .
Число называется остатком, а число - частным.
Пример. Разделим с остатком на . Имеем: . Отсюда остаток равен , а частное равно .
Теорема 1. Пусть даны любые целое число и натуральное число . Тогда разделить на с остатком можно, и притом единственным образом (т.е. числа и из определения деления с остатком существуют и единственны).
Доказательство. Для доказательства существования чисел и надо фактически "измерить" отрезок длины , приняв за единицу измерения отрезок длины . Если , т.е. - натуральное, то надо отложить внутри отрезка длины отрезок длины столько раз, чтобы остаток оказался меньше , так что еще раз отложить уже нельзя. Тогда - число уложившихся отрезков длины . Если , то надо взять . Если , то надо сделать то же самое, но откладывать отрезки длины в левую сторону и дождаться, пока конец очередного отрезка попадет в первый раз левее левого конца отрезка, изображающего , или точно в его конец.
Доказательство единственности можно получить из этой же картинки, а можно
провести методом от противного, что мы сейчас и сделаем. Пусть
разделено на
двумя способами:
Вычитая второе равенство из первого, получим:
имеем, очевидно,
, но в интервале
лишь число
является целым кратным числа
. Поэтому
и
, что и требовалось доказать.
Замечание. Фактически частное и остаток от деления натурального числа на натуральное число находятся по известному способу деления "уголком".
6. Простые числа. Натуральное число называется простым, если его натуральными делителями являются только числа и . Примеры: , , , , - простые числа. Число удобно не считать простым числом.
7. Наибольший общий делитель (НОД) двух целых чисел и , не равных одновременно нулю, - это наибольшее натуральное число , являющееся одновременно делителем для и для , т.е. и . Мы будем обозначать НОД чисел и через . Ясно, что НОД существует, поскольку делитель числа при не может быть больше, чем , где - абсолютная величина (или модуль) числа .
8. Алгоритм Евклида. Вообще алгоритмом называется способ достижения какой-либо цели, описанный так четко, что его может осуществить машина. Алгоритм Евклида - это способ нахождения НОД двух натуральных чисел и .
Предположим для определенности, что
. Разделим
на
с остатком:
Теперь имеется две возможности:
1) . Тогда ясно, что .
2)
. Тогда нужно воспользоваться следующим замечательным
соотношением:
вытекающим из того, что каждый общий делитель
и
делит
и каждый общий делитель
и
делит
(это видно из определения деления с остатком),
так что множество общих делителей
и
совпадает с множеством общих делителей
и
, в частности, совпадают наибольшие общие делители.
Имеем:
Теперь вместо
надо находить
. Деля
на
и обозначая остаток через
, мы получаем:
Если
, то
. Если же
, то надо делить
на
и так далее, пока не получится остаток, равный
. В конце концов это произойдет, поскольку
остатки все время уменьшаются. Последний отличный от нуля
остаток и будет равен
. Окончательно запишем весь процесс так:
Тогда
.
Пример. Вычислим
. Деля число
на число
с остатком, получим
Число
делится на
. Поэтому
.