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

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

Здесь

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

Рис. 19.

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

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

M = m nb n + m n -1 b n -1+… + m 2 b 2+ m 1 b + m 0,

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

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

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

М ≡ S M = m n + m n -1+… + m 2+ m 1+ m 0(mod ( b — 1)),

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

Это, по-видимому, совершенно тривиальное замечание применимо даже в нашей обычной десятичной системе. Мы упоминали в § 5 главы 7, что если мы разобьем цифры десятичного числа на группы по три, то тогда эта группировка может рассматриваться как представление числа при основании b = 10 3= 1000. Аналогично, если группировать цифры в пары, то это соответствует представлению числа при основании b = 10 2= 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».

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

воскресенье = 0,

понедельник = 1,

вторник = 2,

среда = 3,

четверг = 4,

пятница = 5,

суббота = 6.

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

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

365 ≡ 1 (mod 7),

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

366 ≡ 2 (mod 7).

Это показывает, что для обычного года номер W дня недели заданной даты в следующем году увеличится на 1, например, если в этом году 1 января — воскресенье, то в следующем году он будет падать на понедельник. Это не слишком сложно, однако, эта простая схема нарушается високосными годами. Это происходит каждый четвертый год, тогда номер дня недели увеличивается на 2. Более того, возникает дополнительная трудность из-за того, что добавочный день високосного года прибавляется не в начале или конце года, а 29 февраля. Поэтому, для удобства, в общей формуле для вычисления W, которую мы дадим ниже, договоримся считать март — первым месяцем, апрель — вторым и т. д., при этом январь будет одиннадцатым месяцем, а февраль — двенадцатым месяцем предшествующего года.

Но на этом наши трудности не кончаются. В юлианском календаре, введенном по указу Юлия Цезаря, было принято, что год точно равен 365 1/4 дня, в соответствии с правилом високосного года. Однако это не совсем правильно, так как астрономический год в действительности равен 365,2422 дня.

Эта маленькая ошибка вызвала постепенный сдвиг сезонов по отношению к календарю, например, в шестнадцатом веке день весеннего равноденствия (первый день весны) пал на 11 марта вместо 21 марта, как это должно было быть.