У нещодавньому епізоді «Хто хоче стати мільйонером ?» було одне невеличке запитання, над яким Гюнтер Яух явно мав подумати: «Число завжди ділиться на \(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\): У форматі вікторини вони виглядають як невеликі когнітивні пастки, але ведуть безпосередньо до напрочуд елегантної ідеї в теорії чисел.