Ισοτιμίες και αριθμητική υπολοίπων

Η σχέση της ισοτιμίας

Αν σήμερα είναι Δευτέρα, σε $15$ ημέρες θα είναι Τρίτη, και σε $1000$ ημέρες θα είναι Κυριακή: για να το ξέρουμε δεν χρειάζεται να μετρήσουμε τις ημέρες μία προς μία, γιατί αρκεί το υπόλοιπο της διαίρεσης του πλήθους των ημερών με το $7$. Με τον ίδιο τρόπο, $5$ ώρες μετά τις $9$ η ώρα είναι $2$ σε ένα ρολόι $12$ ωρών, και το τελευταίο ψηφίο ενός γινομένου εξαρτάται μόνο από τα τελευταία ψηφία των παραγόντων. Και στις τρεις περιπτώσεις υπολογίζουμε με υπόλοιπα και ξεχνάμε το πηλίκο. Το μάθημα για τη διαιρετότητα και τη διαίρεση με υπόλοιπο μοίρασε τους ακεραίους σε κλάσεις ανάλογα με το υπόλοιπο που αφήνουν όταν διαιρεθούν με έναν φυσικό, και απέδειξε ότι το υπόλοιπο ενός αθροίσματος, ενός γινομένου και μιας δύναμης εξαρτάται μόνο από τα υπόλοιπα των δεδομένων. Το μάθημα αυτό δίνει σε αυτές τις παρατηρήσεις μια δική τους γλώσσα, τη γλώσσα των ισοτιμιών, που εισήγαγε ο Γκάους το 1801 στο έργο του Disquisitiones Arithmeticae, και τη μετατρέπει σε εργαλείο υπολογισμού. Όπως σε εκείνο το μάθημα, οι ακέραιοι χρησιμοποιούνται εκ των προτέρων, με τους κανόνες της αριθμητικής και της διάταξής τους που θεμελιώνονται στο μάθημα για τους ακέραιους αριθμούς.

Ορισμός (ισοτιμία). Έστω $n$ φυσικός. Δύο ακέραιοι $a$ και $b$ είναι ισότιμοι κατά μέτρο $n$ αν ο $n$ διαιρεί τη διαφορά τους $a - b$. Γράφουμε $a \equiv b \pmod{n}$ και διαβάζουμε «ο $a$ είναι ισότιμος με τον $b$ κατά μέτρο $n$»· ο φυσικός $n$ λέγεται μέτρο της ισοτιμίας.

Έτσι, $17 \equiv 2 \pmod{5}$, γιατί $17 - 2 = 15$· $-3 \equiv 9 \pmod{4}$, γιατί $-3 - 9 = -12$· και ένας ακέραιος είναι άρτιος ακριβώς όταν είναι ισότιμος με το $0$ κατά μέτρο $2$. Το ότι ο $a$ είναι πολλαπλάσιο του $n$ γράφεται τώρα $a \equiv 0 \pmod{n}$. Με μέτρο το $1$ όλοι οι ακέραιοι είναι ισότιμοι μεταξύ τους, γιατί το $1$ διαιρεί κάθε ακέραιο· η περίπτωση αυτή δεν έχει ενδιαφέρον, και στα παραδείγματα το μέτρο θα είναι τουλάχιστον $2$. Το σύμβολο $\equiv$, με τις τρεις γραμμές του, θυμίζει το σύμβολο της ισότητας γιατί, όπως θα φανεί, η ισοτιμία συμπεριφέρεται σχεδόν σε όλα όπως εκείνη· η εξαίρεση, η διαίρεση, θα απασχολήσει την παράγραφο για τους αντιστρόφους.

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

Ειδικότερα, κάθε ακέραιος είναι ισότιμος κατά μέτρο $n$ με το υπόλοιπό του, που είναι ένας από τους $n$ ακεραίους $0, 1, \ldots, n - 1$, και με έναν μόνο από αυτούς, γιατί δύο από αυτούς τους ακεραίους είναι τα ίδια τους τα υπόλοιπα και, αν είναι διαφορετικοί, αφήνουν διαφορετικά υπόλοιπα. Ο υπολογισμός κατά μέτρο $n$ συνίσταται στο να αντικαθιστούμε κάθε αριθμό με έναν βολικό αντιπρόσωπο της στήλης του: το υπόλοιπο ή, μερικές φορές, έναν μικρό αρνητικό αριθμό, όπως το $-1$ στη θέση του $n - 1$.