Στο Who Wants to Be a Millionaire, πρόσφατα προέκυψε μια ωραία ερώτηση που ο Günther Jauch έπρεπε ξεκάθαρα να σκεφτεί: «Ένας αριθμός διαιρείται πάντα με το \(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\) modulo ενός αριθμού γίνεται ιδιαίτερα απλή. Για τη διαιρετότητα με \(4\) ο κρίσιμος παράγοντας ήταν ότι \(100 \equiv 0 \pmod 4\) Γίνεται ακόμη πιο ενδιαφέρον όταν οι τιμές \(1\) ή \(-1\) εμφανίζονται αντί για \(0\) .
Ένα κλασικό παράδειγμα είναι η διαιρετότητα με \(11\) .
\[
10 \equiv -1 \pmod{11}
\]
Αν αυτό ισχύει, οι τιμές θέσης ενός δεκαδικού αριθμού modulo \(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.
\]
Ο αρχικός αριθμός έχει το ίδιο υπόλοιπο modulo \(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\) .
Τέτοιοι κανόνες αρχικά φαίνονται να είναι αριθμητικά κόλπα, αλλά τελικά είναι απλώς εφαρμογές της ίδιας ιδέας: αντικατάσταση μεγάλων δυνάμεων του δέκα με απλά υπόλοιπα modulo του εν λόγω αριθμού. Αυτό μετατρέπει έναν μεγάλο δεκαδικό αριθμό σε έναν απλό υπολογισμό που περιλαμβάνει ισοδυναμίες. Αυτός ακριβώς είναι ο λόγος για τον οποίο τέτοιοι κανόνες διαιρετότητας είναι κάτι περισσότερο από απλά αριθμητικά κόλπα. Αντιπροσωπεύουν μια αναγωγή σε υπόλοιπα modulo. \(10^k\): Σε μορφή κουίζ, εμφανίζονται ως μικρές γνωστικές παγίδες, αλλά οδηγούν απευθείας σε μια εκπληκτικά κομψή ιδέα στη θεωρία αριθμών.