Приглашение в теорию чисел

ОРЕ О.

потребовало бы для своей записи

S_N = a_n + a_{n– 1} +… + а₂ + а₁ + а₀ (8.1.2)

фишек. Это число мы называем суммой цифр числа N.

Теперь предположим, что мы хотим выполнить на доске простое действие, а именно: сложить два числа N и M.

Тогда мы должны отметить на доске также второе число

M = (b_m, b_{m– 1}, …, b₂, b₁, b₀)₁₀,

у которого на тех же линиях лежит

S_M = b_m + b_{m– 1} + … + b₂ + b₁ + b₀

складываемых фишек. На некоторых линиях может теперь лежать больше, чем по 9 фишек. Операция, необходимая для нахождения числа N + М, состоит в замене десяти фишек на одной линии одной фишкой на следующей линии. И так нужно продолжать до тех пор, пока такой процесс возможен. На каждом шаге заменяют десять фишек одной-единственной и таким образом происходит потеря девяти фишек на доске. Итак, мы видим, что если сложение выполнено правильно, то число фишек, остающихся на доске, должно удовлетворять условию

S_N+M ≡ S_N + S_M (mod 9), (8.1.3)

т. е. количество фишек, находящихся на доске, должно отличаться от первоначального общего числа фишек на число, кратное 9. Эта проверка (8.1.3) до сих пор сохранила свое старое название «выбрасывание девяток».

После того как это правило было открыто, не составило труда заметить, что оно также применимо при сложении нескольких чисел, при вычитании и при умножении; в последнем случае, в соответствии с (8.1.3),

S_M S_N ≡ S_MN (mod 9). (8.1.4)

Теоретическое доказательство этих правил является легкой задачей при использовании сравнений. Очевидно, что

1 ≡ 1, 10 ≡ 1, 10² ≡ 1, 10³ ≡ 1… (mod 9); (8.1.5)

таким образом, из (8.1.1) и (8.1.2) мы делаем вывод, что

N ≡ S_N (mod 9). (8.1.6)

Поэтому из правил сравнений, которые мы установили в § 3 главы 7, ясно, что

S_N ± S_M ≡ N ± М ≡ S_{N ± M},

S_N • S_M = N •M ≡ S_N•M (mod 9).

Правило

«выбрасывания девяток» чаще всего применяется к умножению. Возьмем в качестве примера числа

M = 3119, N = 3724 (8.1.7)

и их произведение

М • N = 11 614 156.

Это вычисление не может быть верным, так как если бы оно было верным, то мы имели бы, что

M ≡ S_M ≡ 3 + 1 + 1 + 9 ≡ 5 (mod 9),

N ≡ S_N ≡ 3 + 7 + 2 + 4 ≡ 7(mod 9)

и MN ≡ S_MN ≡ 1 + 1 + 6 + 1 + 4 + 1 +5 + 6 ≡ 7 (mod 9).

Но 5 • 7 = 35 ≠ 7 (mod 9).

В действительности же это произведение равно MN = 11 615 156.

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

Рис. 18.

Здесь числа 5 и 7, лежащие слева и справа, означают остатки чисел М и N (по модулю 9), а верхнее число 8 является остатком вычисленного произведения MN. Оно должно проверяться с помощью произведения остатков начальных чисел, записываемого в нижней части.

Здесь

5 • 7 = 35 ≡ 8 (mod 9).

Рис. 19.

Такая проверка «скрещенных костей» была совершенно обычной в ранних изданиях учебников арифметики (рис. 19), например, в английских учебниках семнадцатого и восемнадцатого веков. Конечно, существует возможность, что вычисления содержат ошибку, необнаруживаемую методом «выбрасывания девяток», но тогда мы знаем, что ошибка является «ошибкой по модулю 9».

Ясно, что и при другом основании системы счисления можно использовать простейшую проверку. Для числа

M = m_nbⁿ + m_{n– 1}b^{n– 1} +… + m₂b² + m₁b + m₀,

записанного при основании b, как и в (8.1.5), мы имеем

1 ≡ 1, b ≡ 1, b² ≡ 1… (mod (b — 1));