Στη συνηθισμένη αριθμητική οι αριθμοί 3, 8 και 13 είναι διαφορετικοί. Αν όμως μας ενδιαφέρει μόνο το υπόλοιπο της διαίρεσής τους με το 5, τότε δεν υπάρχει διαφορά μεταξύ τους: και οι τρεις αφήνουν υπόλοιπο 3. Στη γλώσσα της θεωρίας αριθμών λέμε ότι είναι ισότιμοι modulo 5.
Αυτή η αριθμητική θυμίζει το ρολόι. Η ώρα 15:00 και η ώρα 3:00 δείχνουν την ίδια θέση σε ένα δωδεκάωρο καντράν, επειδή η διαφορά τους είναι 12. Οι ισοτιμίες γενικεύουν ακριβώς αυτή την ιδέα.
Η σωστή έννοια και ο συμβολισμός
Έστω \(a,b\in\mathbb Z\) και ένας θετικός ακέραιος \(m\). Λέμε ότι ο \(a\) είναι ισότιμος με τον \(b\) modulo \(m\) και γράφουμε
όταν η διαφορά \(a-b\) διαιρείται ακριβώς με το \(m\). Ισοδύναμα, πρέπει να υπάρχει ακέραιος \(k\) τέτοιος ώστε
Μια τρίτη, απολύτως ισοδύναμη διατύπωση είναι ότι οι \(a\) και \(b\) αφήνουν το ίδιο υπόλοιπο όταν διαιρεθούν με το \(m\). Για παράδειγμα,
επειδή \(38-3=35=7\cdot5\) και \(-2-3=-5=(-1)\cdot5\).
Το \(a\bmod m\) δηλώνει συνήθως το υπόλοιπο της διαίρεσης, δηλαδή έναν αριθμό. Το \(a\equiv b\pmod m\) είναι μια πρόταση που δηλώνει ότι δύο ακέραιοι ανήκουν στην ίδια κλάση υπολοίπου.
Η Ευκλείδεια διαίρεση πίσω από το modulo
Για κάθε ακέραιο \(a\) και κάθε θετικό ακέραιο \(m\), υπάρχουν μοναδικοί ακέραιοι \(q,r\) τέτοιοι ώστε
Ο \(q\) είναι το πηλίκο και ο \(r\) το υπόλοιπο. Αυτό το μοναδικό \(r\) είναι η κανονική τιμή του \(a\bmod m\). Έτσι, για παράδειγμα,
οπότε τόσο το 38 όσο και το \(-2\) έχουν υπόλοιπο 3 modulo 5.
Γιατί πρόκειται για σχέση ισοδυναμίας;
Η ισοτιμία modulo \(m\) χωρίζει τους ακέραιους σε ομάδες επειδή έχει τις τρεις ιδιότητες μιας σχέσης ισοδυναμίας:
\(a\equiv a\pmod m\), αφού \(a-a=0\).
Αν \(a\equiv b\pmod m\), τότε \(b\equiv a\pmod m\).
Αν \(a\equiv b\) και \(b\equiv c\), τότε \(a\equiv c\pmod m\).
Η τελευταία ιδιότητα, για παράδειγμα, ακολουθεί επειδή αν τα \(m\mid(a-b)\) και \(m\mid(b-c)\), τότε το \(m\) διαιρεί και το άθροισμά τους \((a-b)+(b-c)=a-c\).
Οι κλάσεις υπολοίπων
Η κλάση ισοτιμίας ενός ακεραίου \(a\) modulo \(m\) είναι το σύνολο όλων των ακεραίων που είναι ισότιμοι με αυτόν:
Modulo 5 υπάρχουν μόνο πέντε διαφορετικές κλάσεις:
Κάθε ακέραιος ανήκει σε μία και μόνο μία από αυτές. Οι κλάσεις δεν επικαλύπτονται και, αν τις ενώσουμε, παίρνουμε ολόκληρο το \(\mathbb Z\). Με αυτόν τον τρόπο ένα άπειρο σύνολο οργανώνεται σε πεπερασμένο αριθμό «κουτιών», ένα για κάθε δυνατό υπόλοιπο.
Το σύνολο-πηλίκο \(\mathbb Z/m\mathbb Z\)
Το σύνολο όλων των διαφορετικών κλάσεων ισοτιμίας modulo \(m\) ονομάζεται σύνολο-πηλίκο και γράφεται
Συχνά χρησιμοποιείται και ο συντομότερος συμβολισμός \(\mathbb Z_m\), αν και το \(\mathbb Z/m\mathbb Z\) δείχνει καθαρότερα ότι τα στοιχεία είναι κλάσεις ακεραίων και όχι απλώς οι αριθμοί από το 0 έως το \(m-1\).
Στις κλάσεις μπορούμε να προσθέτουμε και να πολλαπλασιάζουμε:
Οι πράξεις είναι καλά ορισμένες: όποιον αντιπρόσωπο μιας κλάσης και αν επιλέξουμε, καταλήγουμε στην ίδια τελική κλάση. Στο \(\mathbb Z/5\mathbb Z\), για παράδειγμα,
Από τον έλεγχο του τελευταίου ψηφίου και τα ημερολόγια μέχρι την κρυπτογραφία και τους κώδικες διόρθωσης σφαλμάτων, η αριθμητική modulo επιτρέπει να αγνοούμε πόσους ολόκληρους κύκλους έχουν περάσει και να κρατάμε μόνο τη θέση μέσα στον κύκλο. Αυτός είναι ο λόγος που μια τόσο απλή ιδέα γίνεται ένα από τα βασικότερα εργαλεία της θεωρίας αριθμών.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου