В недавнем выпуске программы «Кто хочет стать миллионером ?» был задан интересный вопрос, над которым Гюнтеру Яуху явно пришлось задуматься: «Всегда ли число делится на \(4\) без остатка, если число, составленное из его последних двух цифр, равно...?» – и именно здесь нужно на мгновение подумать математически, а не поддаваться соблазну красивых отвлекающих деталей. Потому что, хотя ответы вроде «четное», «содержит \(0\) или «сумма цифр равна \(4\) » звучат правдоподобно на первый взгляд, правильный ответ кроется в простом свойстве нашей десятичной системы.
Число \(X\) делится на \(4\) тогда и только тогда, когда число, образованное его последними двумя цифрами, делится на \(4\) . Доказательство следует непосредственно из десятичного представления. Каждое натуральное число \(X\) может быть однозначно представлено в форме
\[
X = 100 \cdot X' + X''
\]
Запишите, где \(X''\) — число, образованное из последних двух цифр, т.е. \(0 \leq X'' < 100\) , а \(X'\) — предыдущая часть числа. Поскольку
\[
100 = 25 \cdot 4
\]
применяется, следует
\[
X = 25 \cdot 4 \cdot X' + X''.
\]
Первое слагаемое \(25 \cdot 4 \cdot X'\) всегда делится на \(4\) независимо от \(X'\) . Следовательно, для остатка от деления \(X\) на \(4\) имеет значение только \(X''\) . Формально выражено:
\[
X \equiv X'' \pmod{4}.
\]
Это относится, в частности, к:
\[
4 \mid X \iff 4 \mid X''.
\]
Аналогичные правила делимости возникают всякий раз, когда степень числа \(10\) по модулю становится особенно простой. Для делимости на \(4\) решающим фактором является то, что \(100 \equiv 0 \pmod 4\) Это становится еще интереснее, когда вместо \(0\) встречаются значения \(1\) или \(-1\) .
Классическим примером является делимость на \(11\) .
\[
10 \equiv -1 \pmod{11}
\]
Если это так, то разряды десятичного числа по модулю \(11\) всегда чередуются между \(1\) и \(-1\) .
\[
X = a_0 + 10a_1 + 10^2a_2 + 10^3a_3 + \dots
\]
Следовательно, из этого следует
\[
X \equiv a_0 - a_1 + a_2 - a_3 + \dots \pmod{11}.
\]
Число делится на \(11\) тогда и только тогда, когда сумма его чередующихся цифр делится на \(11\) Например, для \(918082\) это так.
\[
2 - 8 + 0 - 8 + 1 - 9 = -22,
\]
и поскольку \(-22\) делится на \(11\) , \(918082\) также делится на \(11\) .
Ещё более элегантным является правило для \(7\) , \(11\) и \(13\) одновременно. Оно гласит, что
\[
1001 = 7 \cdot 11 \cdot 13
\]
и, таким образом
\[
1000 \equiv -1 \pmod{7}, \qquad
1000 \equiv -1 \pmod{11}, \qquad
1000 \equiv -1 \pmod{13}.
\]
Если разделить число на блоки по три справа налево, то можно поочередно складывать и вычитать эти блоки.
\[
X = 123456789
\]
Итак, если учесть
\[
789 - 456 + 123 = 456.
\]
Исходное число имеет тот же остаток по модулю \(7\) , \(11\) и \(13\) , что и \(456\) Следовательно, очень большое число можно заменить значительно меньшим, не изменяя его делимость на эти три числа.
Делимость на \(37\) также имеет удивительно элегантную форму. Поскольку
\[
999 = 27 \cdot 37
\]
применяется
\[
1000 \equiv 1 \pmod{37}.
\]
Если результат делится на \(37\) то блоки из трех чисел можно просто сложить. Например, из
\[
99937
\]
сумма
\[
99 + 937 = 1036.
\]
Там
\[
1036 = 28 \cdot 37
\]
Если \(99937\) делится на 37, то 99937 также делится на \(37\) .
Подобные правила на первый взгляд кажутся числовыми уловками, но в конечном итоге представляют собой лишь применение той же идеи: замена больших степеней десяти простыми остатками по модулю рассматриваемого числа. Это преобразует большое десятичное число в простое вычисление, включающее сравнения. Именно поэтому такие правила делимости — это не просто арифметические уловки; они представляют собой сведение к остаткам по модулю \(10^k\): В формате викторины они кажутся небольшими когнитивными ловушками, но ведут непосредственно к удивительно элегантной идее в теории чисел.