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

≡ S_{N•M< /sub> (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-1b^{n- 1} +… + m₂b² + m₁b + m₀,

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

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

поэтому, как и раньше,

М ≡ S_M = m_n + m_n-1 +… + m₂ + m₁ + m₀ (mod (b — 1)),

и проверочное правило остается прежним.

Это, по-видимому, совершенно тривиальное замечание применимо даже в нашей обычной десятичной системе. Мы упоминали в § 5 главы 7, что если мы разобьем цифры десятичного числа на группы по три, то тогда эта группировка может рассматриваться как представление числа при основании b = 10³ = 1000. Аналогично, если группировать цифры в пары, то это соответствует представлению числа при основании b = 10² = 100.

Рис. 20.

Взяв числа 3119 и 3724 вновь в качестве примера и записав

M = 31 19, N = 37 24, MN = 11 61 51 56,

мы находим

M ≡ 31 + 19 = 50 (mod 99), N ≡ 37 + 24 = 61 (mod 99),

MN ≡ 11 +61+ 51+56 = 179 ≡ 80 (mod 99).

Здесь наша проверка «скрещенных костей» будет такой, как на рис. 20, потому что, как легко видеть, 50 • 61 ≡ 80 (mod 99).

Эта проверка более эффективна, чем «выкидывание девяток», потому что модули в этом случае гораздо больше и вероятность, что ответ будет правильным, соответственно гораздо больше. Другими словами, «ошибка по модулю 99» менее вероятна, чем «ошибка по модулю 9».

§ 2. Дни недели

Многие задачи астрономии и хронологии, связанные с периодичностью, могут быть сформулированы в терминах теоретико-числовых понятий. Возьмем простой пример: определение дня недели, который падает на заданный день. Дни недели повторяются с периодом 7, поэтому вместо обычных названий мы можем дать каждому дню номер:

воскресенье = 0,
понедельник = 1,
вторник     = 2,
среда       = 3,
четверг     = 4,
пятница     = 5,
суббота     = 6.

Если мы это сделаем, то каждому целому числу соответствует день недели, а именно: день, определяемый его остатком по модулю 7.

Если бы мы имели благоприятнейшую ситуацию, при которой количество дней в году делилось на 7, то все даты падали бы на одни и те же дни ежегодно, и составление расписаний было бы гораздо проще, а издатели календарей имели бы меньше работы. Однако количество дней в году равно

365 ≡ 1 (mod 7),

за исключением високосных лет, в которых количество дней

366 ≡ 2 (mod 7).

Это показывает, что для обычного года номер W дня недели заданной даты в следующем году увеличится на 1, например, если в этом году 1 января — воскресенье, то в следующем году