Приглашение в теорию чисел - О. ОРЕ

§ 1. Определение сравнения

Теория чисел имеет свою алгебру, известную, как теория сравнений. Обычная алгебра первоначально развивалась как стенография для операций арифметики. Аналогично, сравнения представляют собой символический язык для делимости, основного понятия теории чисел. Понятие сравнения впервые ввел Гаусс.

Прежде чем мы обратимся к понятию сравнения, сделаем одно замечание о числах, которые будем изучать в этой главе. Мы начали эту книгу, заявив, что будем рассматривать целые положительные числа 1, 2, 3…, и в предыдущих главах мы ограничивались только этими числами и дополнительным числом 0. Но теперь мы достигли стадии, на которой целесообразно расширить наши границы, рассматривая все целые числа:

0, ±1, ±2, ±3….

Это никоим образом не повлияет на наши предыдущие понятия; далее, когда мы будем говорить о простых числах, делителях, наибольших общих делителях и тому подобном, мы будем считать их целыми положительными числами.

Теперь вернемся к языку сравнений. Если а и b — два целых числа и их разность а — b делится на число m, мы выражаем это записью

a ≡ b (mod m) (7.1.1)

которая читается так:

а сравнимо с b по модулю m.

Делитель m мы предполагаем положительным; он называется модулем сравнения. Наше высказывание (7.1.1) означает, что

a — b = mk, где k — целое число. (7.1.2)

Примеры.

1) 23 ≡ 8 (mod 5), так как 23 — 8 = 15 = 5 3;

2) 47 ≡ 11 (mod 9), так как 47–11 = 36 = 9  4;

3) —11 ≡ 5 (mod 8), так как — 11 — 5 = —16 = 8  (-2);

4) 81 ≡ 0 (mod 27), так как 81 — 0 = 81 = 27 3.

Последний пример показывает, что вообще, вместо того, чтобы говорить: число а делится на число m, мы можем записать

a ≡ 0 (mod m),

так как это означает, что

а — 0 = а = mk,

где k — некоторое целое число. Например, вместо того, чтобы сказать, что а — четное число, мы можем записать

a ≡ 0 (mod 2).

Таким же образом видно, что нечетное число является числом, удовлетворяющим сравнению

а ≡ 1 (mod 2).

Эта несколько странная терминология является довольно обычной для математических работ.

§ 2. Некоторые свойства сравнений

Способ, которым мы записываем сравнения, напоминает нам уравнения, и в действительности, сравнения и алгебраические уравнения имеют много общих свойств. Простейшими из них являются три следующих свойства:

a ≡ a (mod m); (7.2.1)

это является следствием того, что

а — а = m — 0,

a ≡ b (mod m) означает, что и b a (mod m). (7.2.2)

Это следует из того, что b — a = — (а — b) = m(—k).

Из

а ≡ b (mod m) и b ≡ c (mod m) (7.2.3)

следует, что а ≡ c (mod m), потому что первые два утверждения означают, что

а — b = mk, b — с = ml,

поэтому

а — с = (а — b) + (b — с) = m (k + l).

Пример. Из того, что 13 ≡ 35 (mod 11) и 35 ≡ — 9 (mod 11) следует, что 13 ≡ — 9 (mod 11).

Мы говорили, что сравнения похожи по своему свойству на равенства. В действительности, мы можем рассматривать равенства как тип сравнения, а именно, сравнения по модулю 0. По определению,

а ≡ b (mod 0)

означает, что

a — b = 0  k = 0

или

а = b.

Вы почти никогда не встретите такую форму сравнения для записи уравнений в математической литературе. Но существует другое сравнение, очевидно, довольно тривиальное, которое иногда используется. Когда модуль есть число m = 1, мы имеем, что

a ≡ b (mod 1)   (7.2.4)

для любой пары целых чисел а и b, так как это означает, что

a — b = 1  k = k (7.2.5)

есть целое число. Но предположим теперь на мгновение, что а и b — произвольные вещественные числа, необязательно целые. Тогда тот факт, что они сравнимы по модулю 1, означает, что их разность есть целое число, т. е. эти два числа имеют одинаковую дробную часть.

Пример. 8 1/3 ≡ 1 1/3 (mod 1), или

8,333… ≡ 1,333… (mod 1).

Вернемся к свойствам обычных сравнений целых чисел; с этого момента мы будем всегда считать, что модуль является целым числом т ≥ 2.

Мы можем разделить числовую ось, начиная от начала координат в обоих направлениях на отрезки длиной m, как на рис. 17. Тогда каждое целое число а, положительное или отрицательное, попадает на один из этих отрезков или на одну из точек деления; таким образом, мы можем записать

a = km + r, (7.2.6)

где k — некоторое целое число, а r— одно из чисел

0, 1, 2…, m — 1. (7.2.7)

Рис. 17.

Это является незначительным обобщением деления положительных чисел, описанного в § 3 главы 4. Здесь мы также называем число r в формуле (7.2.6) остатком при делении числа а на число m или остатком по модулю m.

Примеры.

1) а = 11, m = 7, 11 = 7  1 + 4,

2) а = —11, m = 7, —11 = 7  (—2) + 3.

Деление (7.2.6) может быть также записано как сравнение

а ≡ r (mod m). (7.2.8)

Таким образом, каждое число сравнимо со своим остатком по модулю m. В приведенных выше примерах мы имеем

11 ≡ 4 (mod 7), — 11 ≡ 3 (mod 7).

Никакие два остатка в (7.2.7) не сравнимы по (mod m), так как разность между любыми двумя из них меньше, чем m. Поэтому два числа, которые не сравнимы по (mod m), должны иметь разные остатки. Итак, мы делаем вывод:

сравнение а ≡ b(mod m) выполняется тогда и только тогда, когда числа а и b имеют одинаковые остатки при делении на число m.

Существует другой способ представления этого сравнения. Предположим на мгновение, что а и b — целые положительные числа. Мы видели при обсуждении системы чисел в § 2 главы 6, что когда число а записано при основании m,

а = (аn…, а1, а0)m,

то последняя цифра а0 является остатком числа а при делении его на число m. Если мы используем этот факт, чтобы иначе выразить нашу интерпретацию сравнения, то можно сказать:

сравнение а ≡ b (mod m) выполняется для целых (положительных) чисел а и b тогда и только тогда, когда числа а и b имеют одинаковые последние цифры в записи при основании m.

Например,

37 ≡ 87 (mod 10),

так как эти два числа имеют одну и ту же последнюю цифру в десятичной системе чисел.

Система задач 7.2.

1. Найдите остатки —37(mod 7), — 111 (mod 11), — 365 (mod 30).

§ 3. Алгебра сравнений

Из алгебры мы помним, что уравнения можно складывать, вычитать, умножать. Точно такие же правила справедливы для сравнений. Предположим, что мы имеем сравнения

a ≡ b (mod m), с ≡ d (mod m). (7.3.1)

По определению, это означает, что

a = b + mk, c = d + ml, (7.3.2)

где k и l — целые числа. Сложим уравнения (7.3.2).

В результате получаем

а + с = b + d + m (k + l),

что можем записать как

а + с ≡ b + d (mod m); (7.3.3)

другими словами, два сравнения можно складывать. Таким же образом можно показать, что одно сравнение можно вычитать из другого, т. е. что

a — c ≡ b — d (mod m). (7.3.4)

Пример.

11 ≡ —5 (mod 8) и 7 = — 9 (mod 8). (7.3.5)

Складывая их, получаем

18 ≡ — 14 (mod 8),

а вычитая,

4 ≡ 4 (mod 8).

Оба эти сравнения справедливы.

Можно также перемножить два сравнения. Из (7.3.1) и (7.3.2) следует, что

ac = bd + m(kd + bl + mkl),

таким образом,

ас ≡ bd (mod m). (7.3.6)