Αριθμητική modulo — Μαθηματικά ρολογιού, mod και ισοδυναμία

Η αριθμητική modulo σημαίνει ότι δουλεύουμε με τα υπόλοιπα μετά τη διαίρεση με έναν σταθερό θετικό ακέραιο που λέγεται modulus. Αν δύο αριθμοί αφήνουν το ίδιο υπόλοιπο, συμπεριφέρονται με τον ίδιο τρόπο σε αυτό το modular σύστημα, γι’ αυτό και συχνά τη λένε μαθηματικά ρολογιού.

Σε ένα ρολόι $12$ ωρών, η $13$η ώρα καταλήγει στη $1$, και οι $29$ ώρες καταλήγουν στο ίδιο σημείο με τις $5$ ώρες. Αυτός ο επαναλαμβανόμενος κύκλος είναι η βασική διαίσθηση πίσω από την αριθμητική modulo.

Τι σημαίνει το Mod στην αριθμητική modulo

Για έναν ακέραιο $a$ και έναν θετικό ακέραιο $n$, η παράσταση $a \bmod n$ σημαίνει το υπόλοιπο όταν το $a$ διαιρείται με το $n$.

Παράδειγμα:

$$29 \bmod 12 = 5$$

επειδή

$$29 = 12 \cdot 2 + 5$$

Το modulus είναι το $12$, οπότε αν προσθέσεις ή αφαιρέσεις $12$, δεν αλλάζει το σημείο στο οποίο καταλήγεις μέσα στον κύκλο.

Τι σημαίνει ισοδυναμία modulo $n$

Η ισοδυναμία είναι ο τυπικός τρόπος να πούμε ότι δύο ακέραιοι συμπεριφέρονται το ίδιο modulo $n$.

$$a \equiv b \pmod n$$

σημαίνει ότι τα $a$ και $b$ αφήνουν το ίδιο υπόλοιπο όταν διαιρούνται με το $n$. Ένας ισοδύναμος έλεγχος είναι ο εξής:

$$n \mid (a-b)$$

που σημαίνει ότι «το $n$ διαιρεί το $a-b$».

Άρα

$$29 \equiv 5 \pmod{12}$$

επειδή $29 - 5 = 24$, και το $12$ διαιρεί το $24$.

Αυτή η διάκριση έχει σημασία:

• $29 \bmod 12 = 5$ είναι μια πρόταση για υπόλοιπο.
• $29 \equiv 5 \pmod{12}$ είναι μια πρόταση ισοδυναμίας.

Σχετίζονται, αλλά δεν είναι εναλλάξιμες.

Λυμένο παράδειγμα: $29$ ώρες μετά τις $8$

Έστω ότι τώρα είναι $8$ η ώρα και θέλεις να βρεις τι ώρα θα είναι $29$ ώρες αργότερα σε ρολόι $12$ ωρών.

Πρώτα μείωσε το $29$ modulo $12$:

$$29 \bmod 12 = 5$$

Άρα το να προσθέσεις $29$ ώρες έχει το ίδιο αποτέλεσμα με το να προσθέσεις $5$ ώρες:

$$8 + 29 \equiv 8 + 5 \pmod{12}$$

Έπειτα

$$8 + 29 \equiv 13 \equiv 1 \pmod{12}$$

Άρα το ρολόι δείχνει $1$ η ώρα.

Η βασική κίνηση είναι το βήμα της μείωσης. Στο modulo $12$, η αντικατάσταση του $29$ με το $5$ κρατά την απάντηση ίδια και κάνει τους υπολογισμούς πιο εύκολους.

Γιατί η αρχική μείωση κάνει τα προβλήματα ευκολότερα

Οι μεγάλοι αριθμοί είναι συχνά πιο εύκολοι στον χειρισμό όταν τους αντικαταστήσεις με έναν μικρότερο ισοδύναμο αριθμό.

Για παράδειγμα, modulo $7$,

$$100 \equiv 2 \pmod 7$$

επειδή $100 - 2 = 98$ διαιρείται με το $7$. Αν το πρόβλημα ενδιαφέρεται μόνο για τιμές modulo $7$, μπορείς να δουλέψεις με το $2$ αντί για το $100$.

Συνηθισμένα λάθη

Μπέρδεμα ανάμεσα στην ισότητα και την ισοδυναμία

Το $29 \equiv 5 \pmod{12}$ δεν σημαίνει ότι $29 = 5$. Σημαίνει ότι ανήκουν στην ίδια κλάση υπολοίπων modulo $12$.

Ξεχνάς ότι το modulus έχει σημασία

Το $17 \equiv 5 \pmod{12}$ είναι αληθές, αλλά το $17 \equiv 5 \pmod{10}$ είναι ψευδές. Η ισοδυναμία συνδέεται πάντα με ένα συγκεκριμένο modulus.

Αντιμετωπίζεις το mod σαν συνηθισμένη διαίρεση

Το $29 \bmod 12$ είναι το υπόλοιπο $5$, όχι το πηλίκο $2$ και όχι το κλάσμα $29/12$.

Υποθέτεις ότι το % στο λογισμικό ακολουθεί πάντα την ίδια μαθηματική σύμβαση

Για θετικούς αριθμούς, το % στις γλώσσες προγραμματισμού συχνά ταιριάζει με την έννοια του υπολοίπου που μαθαίνουν πρώτα οι μαθητές. Με αρνητικούς αριθμούς, οι συμβάσεις μπορεί να διαφέρουν, οπότε το αποτέλεσμα ίσως να μην ταιριάζει με το μικρότερο μη αρνητικό υπόλοιπο που χρησιμοποιείται σε πολλά μαθήματα μαθηματικών.

Πού χρησιμοποιείται η αριθμητική modulo

Βλέπεις την αριθμητική modulo κάθε φορά που οι τιμές επαναλαμβάνονται κυκλικά: σε ρολόγια, στις ημέρες της εβδομάδας, σε συστήματα ψηφίων ελέγχου, στο hashing και σε πολλά μέρη της θεωρίας αριθμών.

Εμφανίζεται επίσης στην κρυπτογραφία, αλλά η ίδια βασική ιδέα εξακολουθεί να ισχύει: οι αριθμοί ομαδοποιούνται με βάση τα υπόλοιπά τους και οι ισοδύναμοι αριθμοί μπορούν να θεωρηθούν ισοδύναμοι μέσα σε αυτό το σύστημα.

Δοκίμασε ένα παρόμοιο πρόβλημα

Ποια ημέρα της εβδομάδας είναι $100$ ημέρες μετά από μια Δευτέρα; Αφού οι ημέρες επαναλαμβάνονται modulo $7$, ξεκίνα μειώνοντας το $100$ modulo $7$ πριν απαντήσεις.

Αν θέλεις άλλη μία περίπτωση για σύγκριση, δοκίμασε τη δική σου εκδοχή στο GPAI Solver και δες αν η αρχική μείωση κάνει τη δουλειά πιο σύντομη.