Αριθμητική υπολοίπων

Ο χρόνος περνά σε αυτό το ρολόι χρησιμοποιώντας την αριθμητική modulo 12.

Στα μαθηματικά, η αριθμητική υπολοίπων (αναφέρεται και ως μοδιακή αριθμητική ή με μέτρο) είναι ένα σύστημα αριθμητικής για ακέραιους αριθμούς, όπου οι αριθμοί που απέχουν μία σταθερή ποσότητα (ή πολλαπλάσιο αυτής) είναι ισοδύναμοι (ή ισότιμοι) μεταξύ τους. Έτσι η πρόσθεση δύο αριθμών σε αυτό το σύστημα μπορεί να ερμηνευθεί σαν μία «αναδίπλωση» των τιμών.

Μία γνωστή χρήση της αριθμητικής υπολοίπων είναι για παράδειγμα σε ένα ρολόι των 12 ωρών, το οποίο χωρίζει την μέρα σε δύο περιόδους 12-ωρών. Αν τώρα η ώρα είναι 7:00, τότε σε 8 ώρες αργότερα θα είναι 3:00. Στο συνηθισμένο σύστημα αρίθμησης ο μεταγενέστερος χρόνος θα έπρεπε να πρέπει να είναι 7 + 8 = 15, αλλά αυτό δεν γίνεται στην αριθμητική υπολοίπων, διότι η ώρα του ρολογιού «αναδιπλώνεται» κάθε 12 ώρες και έτσι δεν υπάρχει «η ώρα 15:00». Ομοίως, αν το ρολόι ξεκινά στις 12:00 (το μεσημέρι) και έχουν περάσει 21 ώρες, τότε ο χρόνος θα είναι 9:00 την επόμενη μέρα, αντί για 33:00. Επειδή η ώρα ξεκινά ξανά από την αρχή αφού φτάσει στις 12:00, αυτό είναι αριθμητική modulo 12. Σύμφωνα με τον ορισμό παρακάτω, το 12 είναι ισότιμο όχι μόνο με το 12, αλλά και με το 0, έτσι ώστε ο χρόνος που ονομάζεται "12:00" θα μπορούσε επίσης να ονομάζεται "0:00", αφού το 12 είναι ισότιμο με το 0 modulo 12.

Η σύγχρονη προσέγγιση για την αριθμητική υπολοίπων αναπτύχθηκε από τον Καρλ Φρίντριχ Γκάους, στο βιβλίο του Disquisitiones Arithmeticae, που δημοσιεύθηκε το 1801.

Τρεις σχετικές έννοιες

Θα εισάγουμε τρεις βασικές έννοιες της αριθμητικής υπολοίπων: (1) την δυαδική πράξη mod, (2) την σχέση ισοτιμίας και (3) τις κλάσεις ισοτιμίας Οι αυστηροί ορισμοί δίνονται στις ακόλουθες ενότητες.

H Ευκλείδεια διαίρεση του $a$ με το $n\neq 0$ μας δίνει το πηλίκο $\Pi$ και το υπόλοιπο $\upsilon$ ώστε

$a=\Pi \cdot n+\upsilon$, όπου $0\leq \upsilon <n$.

Το θεώρημα της διαίρεσης λέει ότι το υπόλοιπο είναι μοναδικό, επομένως μπορούμε να ορίσουμε μία συνάρτηση $\operatorname {rem} (a,n)$ που επιστρέφει το υπόλοιπο της διαίρεσης του $a$ με το $n$. Αυτή συνήθως γράφεται ως δυαδικός πράξη mod, δηλαδή

$a{\bmod {n}}$.

Για παράδειγμα, το $14{\bmod {5}}=4$, καθώς $14=2\cdot 5+4$ και $22{\bmod {5}}=2$, καθώς $22=4\cdot 5+2$.

Η σχέση ισοτιμίας είναι μία δυαδική σχέση που συνδέει τους ακεραίους $a,b$ αν έχουν το ίδιο υπόλοιπο με το $n$, και γράφουμε

$a\equiv b{\pmod {n}}$.

Για παράδειγμα, $12\equiv 32{\pmod {5}}$ καθώς και το 12 και το 32 αφήνουν υπόλοιπο $2$ όταν διαιρεθούν με το $5$.

Όπως θα δούμε παρακάτω η σχέση ισοτιμίας με το $n$ χωρίζει τους ακεραίους σε $n$ σύνολα, τις κλάσεις ισοδυναμίας. Για παράδειγμα, για $n=5$ υπάρχουν τα εξής σύνολα

$[0]_{5}=\{\ldots ,-10,-5,0,+5,+10,\ldots \}$,

$[1]_{5}=\{\ldots ,-9,-4,0,+1,+6,\ldots \}$,

$[2]_{5}=\{\ldots ,-8,-3,0,+2,+7,\ldots \}$,

$[3]_{5}=\{\ldots ,-7,-2,0,+3,+8,\ldots \}$,

$[4]_{5}=\{\ldots ,-6,-1,0,+4,+9,\ldots \}$.

Άμα διαλέξουμε έναν ακέραιο από κάθε σύνολο, τότε λαμβάνουμε ένα πλήρες σύστημα υπολοίπων modulo $n$.

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

Ορισμός

Για έναν ακέραιο $n\neq 0$, δύο ακέραιοι $a$ και $b$ λέγονται ισοϋπόλοιποι με μέτρο $n$ (ή ισοϋπόλοιποι modulo $n$)

αν υπάρχει ακέραιος $k$ ώστε $a-b=k\cdot n$,

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

$a\equiv b{\pmod {n}}$, ή $a\equiv _{n}b$.

Παραδείγματα

• Ισχύει ότι

$38\equiv 14{\pmod {12}}$,

καθώς $38-14=24$, το οποίο είναι πολλαπλάσιο του $12$.

$45\equiv 24{\pmod {7}}$,

καθώς $45-24=21$, το οποίο είναι πολλαπλάσιο του $7$.

Αντίστοιχα και για αρνητικές τιμές, ισχύει ότι

$8\equiv -7{\pmod {5}}$,

καθώς $8+7=15$, το οποίο είναι πολλαπλάσιο του $5$.

$2\equiv -3{\pmod {5}}$,

καθώς $2+3=5$, το οποίο είναι πολλαπλάσιο του $5$.

$-18\equiv -3{\pmod {5}}$,

καθώς $-18+3=-15$, το οποίο είναι πολλαπλάσιο του $5$.

Ιδιότητες

Η σχέση της ισοτιμίας με μέτρο $n$ είναι μία σχέση ισοδυναμίας, δηλαδή ικανοποιεί τις εξής ιδιότητες για κάθε $a,b,c\in \mathbb {Z}$:

• (Ανακλαστική ιδιότητα) $a\equiv a{\pmod {n}}$,

Απόδειξη  

Για κάθε $a$, έχουμε ότι $a-a=0=0\cdot n$, άρα (θέτοντας $k=0$)

$a\equiv a{\pmod {n}}$.

• (Συμμετρική ιδιότητα) Αν $a\equiv b{\pmod {n}}$, τότε $b\equiv a{\pmod {n}}$,

Απόδειξη  

Αν $a\equiv b{\pmod {n}}$, τότε υπάρχει $k\in \mathbb {Z}$ ώστε

$a-b=k\cdot n$.

Συνεπώς,

$b-a=(-k)\cdot n$,

και άρα (θέτοντας $k'=-k$), λαμβάνουμε ότι

$b\equiv a{\pmod {n}}$.

• (Μεταβατική ιδιότητα) Αν $a\equiv b{\pmod {n}}$ και $b\equiv c{\pmod {n}}$, τότε $a\equiv c{\pmod {n}}$.

Απόδειξη  

Αν $a\equiv b{\pmod {n}}$ και $b\equiv c{\pmod {n}}$, τότε υπάρχουν $k_{1},k_{2}\in \mathbb {Z}$ ώστε

$a-b=k_{1}\cdot n$

και

$b-c=k_{2}\cdot n$.

Προσθέτοντας αυτές τις δύο κατά μέλη έχουμε ότι

$a-c=k_{1}\cdot n+k_{2}\cdot n=(k_{1}+k_{2})\cdot n$.

Επομένως, θέτοντας $k=k_{1}+k_{2}$ λαμβάνουμε ότι

$a\equiv c{\pmod {n}}$.

Αν

$a_{1}\equiv b_{1}{\pmod {n}}$ και $a_{2}\equiv b_{2}{\pmod {n}},$

τότε ισχύει ότι

• $a_{1}+a_{2}\equiv b_{1}+b_{2}{\pmod {n}}$

Απόδειξη  

Υπάρχουν $k_{1},k_{2}\in \mathbb {Z}$ τέτοια ώστε

$a_{1}-b_{1}=k_{1}\cdot n$,

$a_{2}-b_{2}=k_{2}\cdot n$.

Αθροίζοντας τις δύο παραπάνω έχουμε ότι

${\begin{aligned}&(a_{1}+a_{2})-(b_{1}+b_{2})\\&\quad =(a_{1}-b_{1})+(a_{2}-b_{2})\\&\quad =k_{1}n+k_{2}n\\&\quad =(k_{1}+k_{2})\cdot n\end{aligned}}$

Επομένως, καταλήγουμε ότι

$a_{1}+a_{2}\equiv b_{1}+b_{2}{\pmod {n}}$.

• $a_{1}-a_{2}\equiv b_{1}-b_{2}{\pmod {n}}$,
• $a_{1}a_{2}\equiv b_{1}b_{2}{\pmod {n}}$.

Απόδειξη  

Υπάρχουν $k_{1},k_{2}\in \mathbb {Z}$ τέτοια ώστε

$a_{1}-b_{1}=k_{1}\cdot n$,

$a_{2}-b_{2}=k_{2}\cdot n$.

Αθροίζοντας τις δύο παραπάνω έχουμε ότι

${\begin{aligned}&a_{1}\cdot a_{2}-b_{1}{\dot {b}}_{2}\\&\quad =(b_{1}+k_{1}n)\cdot (b_{2}+k_{2}n)-b_{1}\cdot b_{2}\\&\quad =k_{1}b_{2}n+b_{1}k_{2}n+k_{1}k_{2}n^{2}\\&\quad =(k_{1}b_{2}+b_{1}k_{2}+k_{1}k_{2}n)\cdot n\end{aligned}}$

Επομένως, καταλήγουμε ότι

$a_{1}\cdot a_{2}\equiv b_{1}\cdot b_{2}{\pmod {n}}\,$.

• $a_{1}^{m}\equiv b_{1}^{m}{\pmod {n}}$, για κάθε $m\in \mathbb {N}$.

Απόδειξη  

Προκύπτει επαγωγικά από την προηγούμενη ιδιότητα.

• $P(a_{1})\equiv P(b_{1}){\pmod {n}}$, για κάθε πολυώνυμο $P$.

Για κάθε θετικό ακέραιο $n$ και ακεραίους $a,b,c$, ισχύει ότι

$a\equiv b{\pmod {n}}$ αν και μόνο αν $ac\equiv bc{\pmod {nc}}$.

Απόδειξη  

Ισχύει ότι

$b-a=k\cdot n$

αν και μόνο αν

$c\cdot (b-a)=k\cdot (cn)$,

που δίνει το ζητούμενο.

Για κάθε θετικό ακέραιο $n$ και ακεραίους $a,b,c$, αν ο $c$ είναι σχετικά πρώτος με τον $n$ ισχύει ότι

$ac\equiv bc{\pmod {n}}$ αν και μόνο αν $a\equiv b{\pmod {n}}$.

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

Απόδειξη  

Από την ταυτότητα Μπεζού έχουμε ότι υπάρχουν ακέραιοι $x,y$ τέτοιοι ώστε

$cx+ny=1$.

Αν

$ac\equiv bc{\pmod {n}}$,

τότε υπάρχει ακέραιος $k$, ώστε

$ac-bc=k\cdot n$

Πολλαπλασιάζοντας και τα δύο μέλη με $x$ έχουμε ότι

$(a-b)cx=k\cdot nx$

και χρησιμοποιώντας ότι $cx=1-ny$,

$a-b=kx\cdot n+(a-b)ny=(kx+(a-b)y)\cdot n$.

Καταλήγουμε ότι

$a\equiv b{\pmod {n}}$.

Η αντίστροφη κατεύθυνση προκύπτει από την παραπάνω πολλαπλασιαστική ιδιότητα.

Αν $ac\equiv bc{\pmod {n}}$ και ο μέγιστος κοινός διαιρέτης $d=\operatorname {MK\Delta } (n,c)$, τότε

$a\equiv b{\pmod {n/d}}$.

Απόδειξη  

Η απόδειξη προκύπτει συνδυάζοντας τις παραπάνω δύο ιδιότητες.

Δυαδική πράξη mod

Όπως αναφέραμε παραπάνω η δυαδική πράξη $\operatorname {rem} (a,n)$ ορίζεται ως το υπόλοιπο της Ευκλείδειας διαίρεσης του $a$ με το $n$. Από το θεώρημα της διαίρεσης αυτός είναι ένας μοναδικός ακέραιος. Αντί να γράψουμε $\operatorname {rem} (a,n)$ συνήθως γράφουμε $a{\bmod {b}}$, αλλά δεν πρέπει να συγχέεται με το ${\pmod {n}}$ στην σχέση ισοτιμίας.

Ισχύει η εξής ισοδυναμία μεταξύ των δύο

$a\equiv b{\pmod {n}}$

αν και μόνο αν

$(a{\bmod {n}})=(b{\bmod {n}})$.

Ιδιότητες

• $((a{\bmod {n}})+(b{\bmod {n}})){\bmod {n}}=(a+b){\bmod {n}}$,
• $((a{\bmod {n}})-(b{\bmod {n}})){\bmod {n}}=(a-b){\bmod {n}}$,
• $((a{\bmod {n}})\cdot (b{\bmod {n}})){\bmod {n}}=(ab){\bmod {n}}$,
• $((a{\bmod {n}})^{m}){\bmod {n}}=(a^{m}){\bmod {n}}$,

Συστήματα Υπολοίπων

Κάθε κλάση υπολοίπων modulo $n$ μπορεί να αντιπροσωπεύεται από οποιοδήποτε από τα μέλη της. Συνήθως όμως επιλέγουμε τον μικρότερο μη αρνητικό ακέραιο από την κάθε κλάση (που είναι και το υπόλοιπο της Ευκλείδειας διαίρεσης). Οποιαδήποτε δύο μέλη από διαφορετικές κλάσεις υπολοίπων modulo $n$ δεν είναι ίσα modulo n. Επιπλέον, κάθε ακέραιος ανήκει σε μία και μόνο μία κλάση υπολοίπων modulo n.

Το σύνολο των ακεραίων $\{0,1,2,\ldots ,n-1\}$ λέγεται το ελάχιστο σύστημα υπολοίπων modulo $n$. Οποιοδήποτε σύνολο $n$ ακεραίων, δύο εκ των οποίων δεν είναι ισότιμοι modulo $n$, ονομάζεται πλήρες σύστημα υπολοίπων modulo $n$.

Είναι σαφές ότι το ελάχιστο σύστημα υπολοίπων είναι ένα πλήρες σύστημα υπολοίπων, και ένα πλήρες σύστημα υπολοίπων είναι απλά ένα σύνολο που περιέχει ακριβώς έναν στοιχείο από κάθε κλάση υπολοίπων modulo $n$. Το ελάχιστο σύστημα υπολοίπων modulo $5$ είναι το $\{0,1,2,3,4\}$. Κάποια άλλα πλήρη συστήματα υπολοίπων modulo $5$ είναι:

• $\{1,2,3,4,5\}$,
• $\{12,13,14,15,16\}$,
• $\{-2,-1,0,1,2\}$,
• $\{-13,4,18,25,31\}$.

Μερικά σύνολα τα οποία δεν είναι πλήρη συστήματα υπολοίπων modulo 4 είναι:

• $\{0,6,7,14,22\}$ αφού το $7$ είναι ισότιμο με το $22$ modulo $5$.
• $\{1,3,5\}$ αφού ένα πλήρες σύστημα υπολοίπων modulo $5$ πρέπει να έχει ακριβώς $5$ ασύμβατες κλάσεις υπολοίπων.

Κλάσεις ισοτιμίας

Όπως κάθε σχέση ισοτιμίας, η ισοτιμία modulo $n$ είναι μία σχέση ισοδυναμίας, και η κλάση ισοδυναμίας του ακέραιου $a$, που συμβολίζεται με $[a]_{n}$ ή ${\overline {a}}_{n}$ είναι το σύνολο

$\{\ldots ,a-2n,a-n,a,a+n,a+2n,\ldots \}$.

Αυτό το σύνολο, που αποτελείται από τους ακεραίους που είναι ισότιμοι με το $a$, ονομάζεται κλάση ισοτιμίας ή κλάση υπολοίπων του $a$ modulo $n$.

Ακέραιοι modulo n

Το σύνολο όλων των κλάσεων ισοτιμίας των ακεραίων modulo $n$ ονομάζεται το σύνολο των ακεραίων modulo n, και συμβολίζεται $\mathbb {Z} /n\mathbb {Z}$, $\mathbb {Z} /n$ ή $\mathbb {Z} _{n}$. Το σύνολο ορίζεται ως εξής.

$\mathbb {Z} /n\mathbb {Z} =\left\{[a]_{n}~~|~~a\in \mathbb {Z} \right\}.$

Όταν $n\neq 0$, το $\mathbb {Z} /n\mathbb {Z}$ έχει $n$ στοιχεία και μπορεί να γραφεί ως:

$\mathbb {Z} /n\mathbb {Z} =\left\{[0]_{n},[1]_{n},[2]_{n},\ldots ,[n-1]_{n}\right\}.$

Όταν $n=0$, το $\mathbb {Z} /n\mathbb {Z}$ δεν είναι κενό, αλλά είναι ισομορφικό με το $\mathbb {Z}$, καθώς $[a]_{0}=\{a\}$.

Μπορούμε να ορίσουμε πρόσθεση, αφαίρεση και πολλαπλασιασμό στο σύνολο $\mathbb {Z} /n\mathbb {Z}$ με τους ακόλουθους κανόνες:

• $[a]_{n}+[b]_{n}=[a+b]_{n}$
• $[a]_{n}-[b]_{n}=[a-b]_{n}$
• $[a]_{n}[b]_{n}=[ab]_{n}.$

Το γεγονός ότι οι παραπάνω δυαδικές πράξεις ορίζουν συναρτήσεις προκύπτει επό τις ιδιότητες που αποδείξαμε παραπάνω

Με τον τρόπο αυτό, $\mathbb {Z} /n\mathbb {Z}$ γίνεται ένας αντιμεταθετικός δακτύλιος. Για παράδειγμα, στο δακτύλιο $\mathbb {Z} /24\mathbb {Z}$, έχουμε

$[12]_{24}+[21]_{24}=[9]_{24}$

όπως και στην αριθμητική για το 24-ωρο ρολόι.

Ο συμβολισμός $\mathbb {Z} /n\mathbb {Z}$ χρησιμοποιείται, επειδή είναι ο δακτύλιος πηλίκο του $\mathbb {Z}$ από το ιδεώδες $n\mathbb {Z}$ που περιέχει όλους τους ακεραίους που διαιρούνται με το n, όπου $0\mathbb {Z}$ είναι το μονοσύνολο {0}. Έτσι, το $\mathbb {Z} /n\mathbb {Z}$ είναι ένα σώμα όταν $n\mathbb {Z}$ είναι ένα μεγιστοτικό ιδεώδες, αυτό συμβαίνει, όταν το n είναι πρώτος.

Όσον αφορά τις ομάδες, η κλάση υπολοίπων ${\bar {a_{n}}}$ είναι το σύμπλοκο της a στην ομάδα πηλίκου $\mathbb {Z} /n\mathbb {Z}$, μια κυκλική ομάδα..

Το σύνολο $\mathbb {Z} /n\mathbb {Z}$ έχει μια σειρά από σημαντικές μαθηματικές ιδιότητες που είναι θεμελιώδεις για τους διάφορους κλάδους των μαθηματικών.

Αντί να εξαιρείται η ειδική περίπτωση για n = 0, είναι πιο χρήσιμο να περιλαμβάνει το $\mathbb {Z} /0\mathbb {Z}$ (το οποίο, όπως προαναφέρθηκε, είναι ισομορφικό με το δακτύλιο $\mathbb {Z}$ των ακεραίων), για παράδειγμα, όταν συζητάμε για το χαρακτηριστικό ενός δακτυλίου.

Ο δακτύλιος των ακεραίων modulo n είναι ένα πεπερασμένο σώμα , αν και μόνο αν ο n είναι πρώτος αριθμός. Αν ο n δεν είναι ένας πρώτος με πρωταρχική δύναμη, υπάρχει ένα μοναδικό (μέχρι ισομορφισμό) πεπερασμένο σώμα GF(n) με n στοιχεία, τα οποία δεν πρέπει να συγχέονται με τον δακτύλιο των ακεραίων modulo n, αν και έχουν τον ίδιο αριθμό στοιχείων.

Σχετικά θεωρήματα

Μικρό θεώρημα του Φερμά

To μικρό θεώρημα του Φερμά λέει ότι για κάθε πρώτο αριθμό $p$ και κάθε $a\in \mathbb {Z}$

$a^{p}\equiv a{\pmod {p}}$.

Θεώρημα του Όιλερ

Το θεώρημα του Όιλερ γενικεύει το θεώρημα του Φερμά, και δηλώνει ότι για κάθε $n$ και $a$ που είναι σχετικά πρώτοι μεταξύ τους, ισχύει ότι

$a^{\phi (n)}\equiv 1{\pmod {n}}$,

όπου $\varphi (n)$ είναι η συνάρτηση Όιλερ που μετράει το πλήθος των αριθμών $1,2,\ldots ,n-1$ που είναι σχετικά πρώτοι με το $n$.

Θεώρημα Ουίλσον

Το θεώρημα Ουίλσον λέει ότι ένας φυσικός αριθμός $p$ είναι πρώτος αν και μόνο αν

$(p-1)!\equiv p-1{\pmod {p}}$,

όπου $(p-1)!=1\cdot 2\cdot 3\cdot \ldots \cdot (p-1)$ είναι το παραγοντικό του $p-1$.

Κινέζικο θεώρημα υπολοίπων

Το κινεζικό θεώρημα υπολοίπων λέει ότι για $n_{1},n_{2}$ σχετικά πρώτα μεταξύ τους, το σύστημα γραμμικών ισοτιμιών

$x\equiv a_{1}{\pmod {n_{1}}}$

$x\equiv a_{2}{\pmod {n_{2}}}$

έχει μοναδική λύση modulo $n_{1}n_{2}$ για κάθε $a_{1},a_{2}$.

Εφαρμογές

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

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

Αθλήματα

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

Για παράδειγμα στην επιτραπέζια αντισφαίριση, ο παίχτης που σερβίρει αλλάζει κάθε δύο σερβίς, δηλαδή τα σερβίς πάνε ως εξής $A,A,B,B,A,A,B,B,\ldots$. Αν το σκορ είναι $x$ εναντίον $y$ και $m=(x+y){\bmod {4}}$, τότε ο παίχτης $A$ σερβίρει αν $m=0,1$ διαφορετικά αν $m=2,3$ σερβίρει ο παίχτης $B$ .

Θεωρία κωδικοποίησης

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

Για παράδειγμα, οι διεθνείς πρότυποι αριθμοί βιβλίου (ISBN) που υπάρχουν στο πίσω μέρος των περισσότερων βιβλίων, αποτελούνται από $10$ ψηφία $d_{1},d_{2},\ldots ,d_{10}$, των οποίων το τελευταίο υπολογίζεται από

$d_{10}=10-((10\cdot d_{1}+9\cdot d_{2}+\ldots +2\cdot d_{9}){\bmod {1}}1)$.

Για παράδειγμα, στον αριθμό 1-774-64140-2, το τελευταίο ψηφίο δίνεται από τον τύπο

$11-(10\cdot 0+9\cdot 3+8\cdot 2+7\cdot 1+6\cdot 7+5\cdot 5+4\cdot 1+3\cdot 0+2\cdot 4){\bmod {1}}1=10-9=2$.

Αν είχαμε κάνει κάποιο λάθος σε ένα από τα ψηφία του αριθμού, π.χ. 1-774-64180-2, τότε θα βλέπαμε ότι το $2$ δεν είναι το αναμενόμενο ψηφίο ελέγχου και άρα θα ξέραμε ότι υπήρξε κάπου ένα λάθος.

Αντίστοιχα συστήματα υπάρχουν στους διεθνείς αριθμούς τραπεζικων λογαριασμών (IBAN), και στον αριθμό μητρώου CAS, ένας αριθμός ο οποίος είναι μοναδικός για κάθε χημική ένωση.

Κρυπτογραφία

Στην κρυπτογραφία, η αριθμητική υπολοίπων άμεσα στηρίζει τα συστήματα δημοσίων κλειδιών όπως το RSA και πρωτόκολλο Diffie–Hellman και παρέχει πεπερασμένα πεδία που αποτελούν το θεμέλιο των ελλιπτικών καμπυλών, και χρησιμοποιείται σε πολλούς αλγόριθμους κρυπτογράφησης με συμμετρικά κλειδιά, όπως το Advanced Encryption Standard (AES), το International Data Encryption Algorithm (IDEA), και το RC4. Η κρυπτογράφιση RSA και Diffie–Hellman χρησιμοποιούν εκθετοποίηση με την δυαδική πράξη mod.

Στην άλγεβρα υπολογιστών, η αριθμητική υπολοίπων συνήθως χρησιμοποιείται για να περιορίζει το μέγεθος των ακέραιων συντελεστών σε ενδιάμεσους υπολογισμούς και δεδομένα. Χρησιμοποιείται στην παραγοντοποίηση πολυωνύμου, ένα πρόβλημα για το οποίο όλοι οι γνωστοί αποδοτικοί αλγόριθμοι χρησιμοποιούν αριθμητική υπολοίπων. Χρησιμοποιείται από τις πιο αποδοτικές υλοποιήσεις του μέγιστου κοινού διαιρέτη πολυωνύμου , ακριβή γραμμική άλγεβρα και Gröbner βάση αλγορίθμους πάνω στους ακέραιους και στους ρητούς αριθμούς.

Πληροφορική

Στην πληροφορική, η αριθμητική υπολοίπων χρησιμοποιείται σε αρκετούς αλγορίθμους για την επίλυση διαφόρων προβλημάτων. Για παράδειγμα, στην επεξεργασία κειμένων, οι συναρτήσεις κατακερματισμού χρησιμοποιούνται για την επιτάχυνση της σύγκρισης συμβολοσειρών. Πιο συγκεκριμένα, αν έχουμε δύο συμβολοσειρές $a$ και $b$ αντί να συγκρίνουμε τους χαρακτήρες τους έναν-προς έναν, υπολογίζουμε έναν ακέραιο $h(a)$ και έναν ακέραιο $h(b)$, και πρώτα ελέγχουμε αν $h(a)=h(b)$. Αν δεν είναι ίσα, τότε οι συμβολοσειρές δεν μπορεί να είναι ίσες. Διαφορετικά, πρέπει να κάνουμε τον αργό έλεγχο χαρακτήρα προς χαρακτήρα.

Για παράδειγμα, μία τέτοια συνάρτηση μπορεί να είναι η

$h(s)=((s_{1}-{\texttt {a}})+(s_{2}-{\texttt {a}})+\ldots +(s_{n}-{\texttt {a}})){\bmod {2}}4$.

Αν $a={\texttt {catbat}}$ και $b={\texttt {catbot}}$, τότε

$h({\texttt {catbat}})=(2+0+19+1+0+19){\bmod {2}}4=17$,

$h({\texttt {catbot}})=(2+0+19+1+14+19){\bmod {2}}4=7$.

Στην συγκεκριμένη περίπτωση, συγκρίνοντας τα $h(a)$ και $h(b)$, βλέπουμε ότι είναι διαφορετικά άρα και οι συμβολοσειρές είναι διαφορετικές, άρα μπορούμε να αποφείγουμε να συγκρίνουμε τους έξι χαρακτήρες των συμβολοσειρών.

Μουσική

Στη μουσική, το modulo 12 χρησιμοποιείται στην εξέταση του συστήματος του δωδεκάτονου ίσου τέμπου, όπου προκύπτει η οκτάβα και η εναρμόνια ισοδυναμία (δηλαδή, τόνος σε 1∶2 ή 2∶1 αναλογία είναι ισοδύναμα, και η C-Δίεση θεωρείται η ίδια ως D-ύφεση).

Νοεροί υπολογισμοί

Η μέθοδος casting out nines προσφέρει ένα γρήγορο έλεγχο των δεκαδικών αριθμητικών υπολογισμών που εκτελούνται με το χέρι. Βασίζεται στην αριθμητική υπολοίπων modulo 9, και συγκεκριμένα στην κρίσιμη ιδιότητα όπου 10 ≡ 1 (mod 9).

Ημερολόγια

Το modulo 7 χρησιμοποιείται σε αλγορίθμους που προσδιορίζουν την ημέρα της εβδομάδας για μια συγκεκριμένη ημερομηνία. Ειδικότερα, η συνεκτικότητα Zeller και ο αλγόριθμος της ημέρας της κρίσεως κάνουν μεγάλη χρήση του modulo-7.

Άλλοι κλάδοι

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

Υπολογιστική πολυπλοκότητα

Από τη στιγμή που η αριθμητική υπολοίπων έχει ένα τέτοιο ευρύ φάσμα εφαρμογών, είναι σημαντικό να γνωρίζουμε πόσο αποδοτικα μπορούν να υλοποιηθούν οι διάφορες πράξεις. Για παράδειγμα, η πρόσθεση, η αφαίρεση και ο πολλαπλασιασμός δύο αριθμών με ${\displaystyle }$ ψηφία μπορεί να γίνει σε $\Theta (d)$ χρόνο. Η ύψωση σε μία δύναμη modulo $n$ μπορεί επίσης να γίνει αποδοτικά σε χρόνο $\Theta (d^{2})$ με την χρήση της δυαδικής εκθετοποίησης Ένα γραμμικό σύστημα ισοτιμιών μπορεί να λυθεί σε πολυωνυμικό χρόνο με μια μορφή απαλοιφής Γκάους, για περισσότερες λεπτομέρειες δείτε το κινεζικό θεώρημα υπολοίπων.

Η αναγωγή Μοντγκόμερι είναι μία τεχνική στις υλοποιήσεις που επιτρέπει διάφορες πράξεις modulo $n$ (όπως η πρόσθεση, η αφαίρεση, ο πολλαπλασιασμός και η ύψωση σε κάποια δύναμη), να εκτελούνται αποδοτικά σε μικρότερα υπόλοιπα modulo $n_{1},n_{2}$ και μετά να μετατρέπονται σε υπόλοιπα modulo $n$.

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

Στις γλώσσες προγραμματισμού

Στις γλώσσα προγραμματισμού, η δυαδική πράξη mod συνήθως αναφέρεται είτε με το σύμβολο "%" (για παράδειγμα, στις C, C++, Java, JavaScript, Perl, Python και Scala) ή με "mod" (για παράδειγμα, σε Pascal, BASIC, SQL, Haskell, ABAP, και MATLAB), με εξαιρέσεις (για παράδειγμα, το Excel).

Οι εν λόγω τελεστές συχνά αναφέρονται ως "mod", αλλά συνήθως διαφέρουν από τον μαθηματικό ορισμό. Για παράδειγμα, στην C++ αν το πρώτο επιχείρημα είναι αρνητικό, θα επιστραφεί ένας αρνητικός αριθμός, και στην Python αν το δεύτερο επιχείρημα είναι αρνητικό ένας αρνητικός αριθμός θα επιστραφεί. Η δυαδική modulo αντί mod, όπως 38 ≡ 14 (modulo 12) μερικές φορές χρησιμοποιείται για να δηλώσει το μαθηματικό υπόλοιπο και όχι απλά ένα υπόλοιπο (για παράδειγμα, στη Ruby).

Παράδειγμα

Οι περισσότερες γλώσσες προγραμματισμού υποστηρίζουν τον υπολογισμό υπολοίπων. Για παράδειγμα, στην C/C++/Java έχουν την πράξη %, που επιτρέπει να γράψουμε

int a = 53;
int b = 23;
int m = 100;
int res = (a * b) % m; // res=19.

Ένα πιθανό πρόβλημα με αυτή την υλοποίηση είναι ότι ο τύπος int, κρατάει αριθμούς με περιορισμένο πλήθος δυαδικών ψηφίων (συνήθως 16 ή 32). Αυτό σημαίνει ότι αν ο a και ο b είναι αρκετά μεγάλοι, τότε το γινόμενο τους μπορεί να υπερχειλίσει, παρόλο που το αποτέλεσμα χωράει σε int (πχ όταν $a=2^{31}-1$).

Υλοποιήσεις

Παρακάτω δίνονται δύο αρκετά γρήγορες υλοποιήσεις C για την εκτέλεση πολλαπλασιασμού υπολοίπων στους μη προσημασμένους ακεραίους όχι μεγαλύτερους από 63 bits, αποφεύγοντας κάποια πιθανή υπερχείλιση στις ενδιάμεσες πράξεις. Ο πρώτος είναι ο εξής:

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) {
   uint64_t d = 0, mp2 = m >> 1;
   int i;
   if (a >= m) a %= m;
   if (b >= m) b %= m;
   for (i = 0; i < 64; ++i) {
      d = (d > mp2) ? (d << 1) - m : d << 1;
      if (a & 0x8000000000000000ULL) d += b;
      if (d > m) d -= m;
      a <<= 1;
   }
   return d;
}

Στις αρχιτεκτονικές των υπολογιστών, όπου μια εκτεταμένης ακριβείας μορφή, με τουλάχιστον 64 bits mantissa, είναι διαθέσιμη (όπως ο long double τύπος των περισσοτέρων x86 C compilers), η παρακάτω συνάρτηση μπορεί να χρησιμοποιηθεί. Κάνει χρήση του πολλαπλασιασμού κινητής υποδιαστολής και ότι το αποτέλεσμα διατηρεί τα πιο σημαντικά bits του γινομένου, τα οποία θα χανόντουσαν αν χρησιμοποιούσαμε τον αντίστοιχο πολλαπλασιασμό ακεραίων (λόγω της υπερχείλισης).

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) {
   long double x;
   uint64_t c;
   int64_t r;
   if (b >= m) b %= m;
   x = a;
   c = x * b / m;
   r = (int64_t)(a * b - c * m) % (int64_t)m;
   return r < 0 ? r + m : r;
}

Ωστόσο, και για τις δύο ρουτίνες για να λειτουργήσουν, το m δεν πρέπει να υπερβαίνει τα 63 bits.

Δείτε επίσης

• Ευκλείδεια διαίρεση
• Κινεζικό Θεώρημα Υπολοίπων
• Θεώρημα του Όιλερ
• Μικρό θεώρημα του Φερμά

Πηγές

• Anthony Gioia, Number Theory, an IntroductionReprint (2001) Dover. ISBN 0-486-41449-3
• Long, Calvin T. (1972). Elementary Introduction to Number Theory (2nd έκδοση). Lexington: D. C. Heath and Company. LCCN 77171950. 
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall