Глава I. Целые числа

Лекция 1. Деление натуральных чисел с остатком.
Простые числа. Алгоритм Евклида

Часть математики, изучающая целые числа, называется арифметикой или теорией чисел. Это один из самых красивых разделов математики. Хотя школьники знакомятся с ним очень рано, он является довольно трудным. В арифметике имеется много задач, еще не решенных учеными, хотя их формулировку может понять даже первоклассник. О некоторых из них будет идти речь ниже.

Сначала опишем объекты, о которых пойдет речь.

1. Натуральные числа - это числа $1$ , $2$ , $3$ , ... Они возникают в процессе счета и означают количество предметов. Множество всех натуральных чисел обозначается через $\QTR{bf}{N}$ .

2. Целые числа - это числа ..., $-3$ , $-2$ , $-1$ , $0$ , $1$ , $2$ , $3$ , ..., т.е. число $0$ , натуральные числа и числа, противоположные по знаку натуральным. Множество всех целых чисел обозначается через $\QTR{bf}{Z}$ . Натуральные числа можно складывать и умножать. Вычитание натуральных чисел определяется как операция, обратная сложению. А именно, равенство $a-b=c$ означает, что $a+b=c$ . Это вычитание выполнимо не всегда, а лишь в том случае, когда $a>b$ . В множестве целых чисел вычитание натуральных чисел всегда выполнимо. А именно, надо положить $a-a=0$ , а если $a<b$ , то $a-b=-(b-a)$ . Сложение любых целых чисел и их вычитание, а также умножение выполняются с помощью известных правил знаков.

3. Свойства арифметических операций хорошо известны. Они часто используются без специального упоминания о них. Всюду в дальнейшем буквы $a$ , $b$ , $c$ означают любые целые числа.

  1. $(a+b)+c=a+(b+c)$
    $a+b=b+a$
    $a+0=a$
    $a+(-a)=0$

  2. $(ab)c=a(bc)$
    $ab=ba$
    $a1=a$

  3. $a(b+c)=ab+ac$

  4. Если $ab=0$ , то $a=0$ или $b=0$

Следствие. Если $ax_1=b$ , $ax_2=b$ и $a\ne 0$ , то $x_1=x_2$ , т.е. уравнение $ax=b$ имеет не более одного решения в целых числах.

4. Делимость. Определение. Пусть $a$ , $d$ - целые числа. Говорят, что $d$ - делитель $a$ , или что $d$ делит $a$ , или что $a$ кратно $d$ ( $a$ - кратное $d$ ), или что $a$ делится на $d$ , если существует такое целое число $k$ , что $a=dk$ . Записывают этот факт в виде: $d\mid a$ .

Упражнение. Докажите, что

если $d\mid a$ и $d\mid b$ , то $d\mid (a+b)$ и $d\mid (a-b)$ ;

если $d\mid a$ и $c$ - любое целое число, то $d\mid ac$ .

Проследите, какие из правил, приведенных в п. 3, здесь применяются.

5. Деление с остатком. Определение. Пусть $a$ - целое, $d$ - натуральное число. Разделить с остатком $a$ на $d$ - значит найти такие целые числа $q$ и $r$ , что $a=dq+r$ , где число $r$ таково, что $0\le r<d$ .

Число $r$ называется остатком, а число $q$ - частным.

Пример. Разделим с остатком $-10$ на $4$ . Имеем: $-10=4\cdot(-3)+2$ . Отсюда остаток равен $2$ , а частное равно $-3$ .

Теорема 1. Пусть даны любые целое число $a$ и натуральное число $d$ . Тогда разделить $a$ на $d$ с остатком можно, и притом единственным образом (т.е. числа $q$ и $r$ из определения деления с остатком существуют и единственны).

Доказательство. Для доказательства существования чисел $q$ и $r$ надо фактически "измерить" отрезок длины $a$ , приняв за единицу измерения отрезок длины $d$ . Если $a>0$ , т.е. $a$ - натуральное, то надо отложить внутри отрезка длины $a$ отрезок длины $d$ столько раз, чтобы остаток $r$ оказался меньше $d$ , так что еще раз $d$ отложить уже нельзя. Тогда $q$ - число уложившихся отрезков длины $d$ . Если $a=0$ , то надо взять $q=r=0$ . Если $a<0$ , то надо сделать то же самое, но откладывать отрезки длины $d$ в левую сторону и дождаться, пока конец очередного отрезка попадет в первый раз левее левого конца отрезка, изображающего $a$ , или точно в его конец.

Доказательство единственности можно получить из этой же картинки, а можно провести методом от противного, что мы сейчас и сделаем. Пусть $a$ разделено на $d$ двумя способами:
MATH Вычитая второе равенство из первого, получим:
MATH имеем, очевидно, $-d<r_1-r_2<d$ , но в интервале $(-d,d)$ лишь число $0$ является целым кратным числа $d$ . Поэтому $r_1=r_2$ и $q_1=q_2$ , что и требовалось доказать.

Замечание. Фактически частное и остаток от деления натурального числа $a$ на натуральное число $d$ находятся по известному способу деления "уголком".

6. Простые числа. Натуральное число $p\ge 2$ называется простым, если его натуральными делителями являются только числа $1$ и $p$ . Примеры: $2$ , $3$ , $5$ , $7$ , $11$ - простые числа. Число $1$ удобно не считать простым числом.

7. Наибольший общий делитель (НОД) двух целых чисел $a$ и $b$ , не равных одновременно нулю, - это наибольшее натуральное число $d$ , являющееся одновременно делителем для $a$ и для $b$ , т.е. $d\mid a$ и $d\mid b$ . Мы будем обозначать НОД чисел $a$ и $b$ через $(a,b)$ . Ясно, что НОД существует, поскольку делитель числа $a$ при $a\ne 0$ не может быть больше, чем $|a|$ , где $|a|$ - абсолютная величина (или модуль) числа $a$ .

8. Алгоритм Евклида. Вообще алгоритмом называется способ достижения какой-либо цели, описанный так четко, что его может осуществить машина. Алгоритм Евклида - это способ нахождения НОД двух натуральных чисел $a$ и $b$ .

Предположим для определенности, что $a\ge b$ . Разделим $a$ на $b$ с остатком:
MATH

Теперь имеется две возможности:

1) $r=0$ . Тогда ясно, что $(a,b)=b$ .

2) $r>0$ . Тогда нужно воспользоваться следующим замечательным соотношением:
MATH вытекающим из того, что каждый общий делитель $a$ и $b$ делит $r$ и каждый общий делитель $b$ и $r$ делит $a$ (это видно из определения деления с остатком), так что множество общих делителей $a$ и $b$ совпадает с множеством общих делителей $b$ и $r$ , в частности, совпадают наибольшие общие делители. Имеем:
MATH Теперь вместо $(a,b)$ надо находить $(b,r)$ . Деля $b$ на $r$ и обозначая остаток через $r_1$ , мы получаем:
MATH Если $r_1=0$ , то $(a,b)=(b,r)=r$ . Если же $r_1\ne 0$ , то надо делить $r$ на $r_1$ и так далее, пока не получится остаток, равный $0$ . В конце концов это произойдет, поскольку остатки все время уменьшаются. Последний отличный от нуля остаток и будет равен $(a,b)$ . Окончательно запишем весь процесс так:
MATH MATH Тогда $(a,b) = r_n$ .

Пример. Вычислим MATH . Деля число $987654321$ на число $123456789$ с остатком, получим
MATH Число $123456789$ делится на $9$ . Поэтому MATH .