W niedawnym odcinku programu „Milionerzy ?” padło sprytne pytanie, nad którym Günther Jauch najwyraźniej musiał się zastanowić: „Liczba jest zawsze podzielna przez \(4\) bez reszty, jeśli liczba utworzona z dwóch ostatnich cyfr to…?” – i właśnie w tym momencie trzeba przez chwilę pomyśleć matematycznie, zamiast dać się zwieść ładnym rozproszeniom. Bo choć odpowiedzi takie jak „jest parzysta”, „zawiera \(0\) lub „suma cyfr wynosi \(4\) ” brzmią wiarygodnie na pierwszy rzut oka, poprawna odpowiedź leży w prostej właściwości naszego systemu dziesiętnego.
Liczba \(X\) jest podzielna przez \(4\) wtedy i tylko wtedy, gdy liczba utworzona przez jej dwie ostatnie cyfry jest podzielna przez \(4\) . Dowód wynika bezpośrednio z zapisu dziesiętnego. Każdą liczbę naturalną \(X\) można jednoznacznie przedstawić w postaci
\[
X = 100 \cdot X' + X''
\]
napisz, gdzie \(X''\) to liczba utworzona z dwóch ostatnich cyfr, tj. \(0 \leq X'' < 100\) , a \(X'\) to poprzednia część liczby. Ponieważ
\[
100 = 25 \cdot 4
\]
dotyczy, następuje
\[
X = 25 \cdot 4 \cdot X' + X''.
\]
Pierwszy składnik \(25 \cdot 4 \cdot X'\) jest zawsze podzielny przez \(4\) niezależnie od \(X'\) . Zatem dla reszty z \(X\) po podzieleniu przez \(4\) istotne jest tylko \(X''\) . Formalnie wyrażone:
\[
X \equiv X'' \pmod{4}.
\]
Dotyczy to w szczególności:
\[
4 \mid X \iff 4 \mid X''.
\]
Podobne zasady podzielności pojawiają się, gdy potęga \(10\) modulo staje się szczególnie prosta. W przypadku podzielności przez \(4\) kluczowym czynnikiem było to, że \(100 \equiv 0 \pmod 4\) Staje się to jeszcze bardziej interesujące, gdy zamiast \(0\) występują wartości \(1\) lub \(-1\) .
Klasycznym przykładem jest podzielność przez \(11\) .
\[
10 \equiv -1 \pmod{11}
\]
Jeżeli jest to prawdą, wartości miejsc liczby dziesiętnej modulo \(11\) zawsze będą zmieniać się pomiędzy \(1\) i \(-1\) .
\[
X = a_0 + 10a_1 + 10^2a_2 + 10^3a_3 + \dots
\]
W związku z tym następuje
\[
X \equiv a_0 - a_1 + a_2 - a_3 + \dots \pmod{11}.
\]
Liczba jest podzielna przez \(11\) wtedy i tylko wtedy, gdy suma jej naprzemiennych cyfr jest podzielna przez \(11\) Na przykład w przypadku \(918082\) jest tak.
\[
2 - 8 + 0 - 8 + 1 - 9 = -22,
\]
a ponieważ \(-22\) jest podzielne przez \(11\) , \(918082\) jest również podzielne przez \(11\) .
Jeszcze bardziej elegancka jest reguła dla \(7\) , \(11\) i \(13\) jednocześnie. Obowiązuje ona,
\[
1001 = 7 \cdot 11 \cdot 13
\]
a zatem
\[
1000 \equiv -1 \pmod{7}, \qquad
1000 \equiv -1 \pmod{11}, \qquad
1000 \equiv -1 \pmod{13}.
\]
Jeśli podzielisz liczbę na bloki po trzy od prawej do lewej, możesz naprzemiennie dodawać i odejmować te bloki.
\[
X = 123456789
\]
Więc jeśli weźmiemy pod uwagę
\[
789 - 456 + 123 = 456.
\]
Liczba oryginalna ma tę samą resztę modulo \(7\) , \(11\) i \(13\) co \(456\) Zatem bardzo dużą liczbę można zastąpić znacznie mniejszą, nie zmieniając jej podzielności przez te trzy liczby.
Podzielność przez \(37\) ma również zaskakująco elegancką formę. Ponieważ
\[
999 = 27 \cdot 37
\]
dotyczy
\[
1000 \equiv 1 \pmod{37}.
\]
Gdy liczba jest podzielna przez \(37\) bloki po trzy można po prostu dodać. Na przykład, z
\[
99937
\]
suma
\[
99 + 937 = 1036.
\]
Tam
\[
1036 = 28 \cdot 37
\]
Jeśli \(99937\) jest podzielne przez 37, to 99937 jest również podzielne przez \(37\) .
Takie reguły początkowo wydają się być sztuczkami numerycznymi, ale ostatecznie są jedynie zastosowaniem tej samej idei: zastąpienia dużych potęg dziesięciu prostymi resztami modulo danej liczby. To przekształca dużą liczbę dziesiętną w proste obliczenie z uwzględnieniem kongruencji. Właśnie dlatego takie reguły podzielności to coś więcej niż zwykłe sztuczki arytmetyczne; stanowią one redukcję do reszt modulo. \(10^k\): W formie quizu jawią się jako drobne pułapki poznawcze, ale prowadzą bezpośrednio do zaskakująco eleganckiej idei w teorii liczb.