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