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

Στην θεωρία αριθμών, το κινεζικό θεώρημα των υπολοίπων (γνωστό και ως θεώρημα υπολοίπων του Νικόμαχου), αναφέρει ότι αν γνωρίζουμε τα υπόλοιπα $m_{1},m_{2}$ ενός ακεραίου $x$ με τους ακεραίους $n_{1},n_{2}$ που είναι σχετικά πρώτοι μεταξύ τους, τότε μπορούμε να υπολογίσουμε το υπόλοιπο του $x$ με το γινόμενό τους $n_{1}\cdot n_{2}$.< Επίσης δίνει και έναν αποδοτικό τρόπο υπολογισμού του βασισμένο στον αλγόριθμο του Ευκλείδη.

Για παράδειγμα, αν γνωρίζουμε ότι

$x\equiv 2{\pmod {3}}$ και $x\equiv 3{\pmod {5}}$,

τότε (όπως θα δούμε παρακάτω) προκύπτει ότι

$x\equiv 8{\pmod {15}}$.

Αυτό μπορεί να επαληθευφθεί και από τον παρακάτω πίνακα υπολοίπων

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Υπόλοιπο με το $3$	0	1	2	0	1	2	0	1	2	0	1	2	0	1	2
Υπόλοιπο με το $5$	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4

Πιο γενικά, αν γνωρίζουμε τα υπόλοιπα $m_{1},m_{2},\ldots ,m_{k}$ ενός ακεραίου $x$ με διάφορους ακεραίους $n_{1},n_{2},\ldots ,n_{k}$, τότε μπορούμε να υπολογίσουμε το υπόλοιπο του $x$ με το γινόμενο $n_{1}n_{2}\cdot \cdots \cdot n_{k}$, αρκεί οι ακέραιοι να είναι σχετικά πρώτοι μεταξύ τους.

Το θεώρημα αναφέρεται για πρώτη φορά τον 3ο αι. από τον Κινέζο μαθηματικό Σουνζί στο έργο του "Τα κλασικά μαθηματικά του διδασκάλου Σουν". Χρησιμοποιείται σε υπολογισμούς σε μεγάλους αριθμούς, καθώς μας επιτρέπει να αντικαθιστούμε έναν υπολογισμό από ορισμένους υπολογισμούς σε μικρότερους αριθμούς.

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

Ιστορία

Στο έργο του Σουανζί αναφέρεται το εξής πρόβλημα: "Ένα σύνολο αντικειμένων, αν το μετρήσω ανά 3 περισσεύουν 2, αν το μετρήσω ανά 5 περισσεύουν 3 και αν το μετρήσω ανά 7 περισσεύουν 2. Πόσα είναι τα αντικείμενα;". Δεν αναφέρεται απόδειξη ή ο αλγόριθμος της λύσης. Αυτός δόθηκε τον 6ο αι. από τον Αριαμπάτα. Ειδικές περιπτώσεις του θεωρήματος ήταν γνωστές στον Βραχμαγκούπτα τον 7ο αι. και εμφανίζονται το 1202 στο έργο "Liber Abaci" του Φιμπονάτσι. Το αποτέλεσμα αργότερα γενικεύτηκε με την πλήρη λύση το 1247 στο έργο "Μαθηματικά δοκίμια σε Εννέα Κεφάλαια" του Κιν Γιουσάο.

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

Διατύπωση

Έστω $n_{1}$ και $n_{2}$ δύο φυσικοί αριθμοί σχετικά πρώτοι μεταξύ τους. Τότε, για κάθε $m_{1},m_{2}$, υπάρχει $x$ ώστε

$x\equiv m_{1}{\pmod {n_{1}}}$, και

$x\equiv m_{2}{\pmod {n_{2}}}$,

και για κάθε $x_{1},x_{2}$ που ικανοποιούν αυτές τις σχέσεις ισχύει ότι

$x_{1}\equiv x_{2}{\pmod {n_{1}n_{2}}}$.

Γενική λύση

Αφού $n_{1},n_{2}$ είναι σχετικά πρώτοι μεταξύ τους, από την ταυτότητα Μπεζού ισχύει ότι υπάρχουν ακέραιοι $a_{1},a_{2}$ τέτοιοι ώστε

$a_{1}n_{1}+a_{2}n_{2}=1$.

Η γενική λύση του παραπάνω συστήματος δίνεται από

$x=a_{1}n_{1}m_{2}+a_{2}n_{2}m_{1}+n_{1}n_{2}\cdot t$ για κάθε $t\in \mathbb {Z}$.

Ως ισομορφισμός

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

$f(x)=(x{\bmod {n_{1}}},x{\bmod {n_{2}}})$

είναι ισομορφισμός μεταξύ των συνόλων $\mathbb {Z} _{n_{1}\cdot n_{2}}$ και $\mathbb {Z} _{n_{1}}\times \mathbb {Z} _{n_{2}}$.

Αποδείξεις

Απόδειξη μοναδικότητας  

Έστω $x_{1},x_{2}$ δύο ακέραιοι που ικανοποιούν τις παραπάνω σχέσεις. Από την πρώτη σχέση

$x_{1}\equiv m_{1}{\pmod {n_{1}}}$,

$x_{2}\equiv m_{1}{\pmod {n_{1}}}$,

έχουμε ότι υπάρχουν ακέραιοι $k_{1},k_{2}$ τέτοιοι ώστε

$x_{1}=m_{1}+n_{1}\cdot k_{1}$,

$x_{2}=m_{1}+n_{1}\cdot k_{2}$.

Από την δεύτερη σχέση έχουμε ότι

$x_{1}\equiv x_{2}{\pmod {n_{2}}}$

και επομένως

$m_{1}+n_{1}\cdot k_{1}\equiv m_{1}+n_{1}\cdot k_{2}{\pmod {n_{2}}}$,

δηλαδή

$n_{1}\cdot k_{1}\equiv n_{1}\cdot k_{2}{\pmod {n_{2}}}$.

Αφού $n_{1}$ και $n_{2}$ είναι σχετικά πρώτοι μεταξύ τους, το $n_{1}$ έχει πολλαπλασιαστικό αντίστροφο mod $n_{2}$, δηλαδή

$n_{1}^{-1}\cdot n_{1}\cdot k_{1}\equiv n_{1}^{-1}\cdot n_{1}\cdot k_{2}{\pmod {n_{2}}}\Leftrightarrow k_{1}\equiv k_{2}{\pmod {n_{2}}}$,

Επομένως, υπάρχει ακέραιος $\ell$ ώστε $k_{2}=k_{1}+n_{2}\cdot \ell$ και έτσι

${\begin{aligned}x_{2}&=m_{1}+n_{1}\cdot (k_{1}+n_{2}\cdot \ell )\\&\equiv m_{1}+n_{1}k_{1}{\pmod {n_{1}n_{2}}}\\&\equiv x_{1}{\pmod {n_{1}n_{2}}}.\end{aligned}}$

Καταλήγουμε ότι όλες οι λύσεις του συστήματος είναι ισοϋπόλοιπες mod $n_{1}n_{2}$.

Απόδειξη ύπαρξης  

Από την απόδειξη μοναδικότητας έχουμε ότι η συνάρτηση $f:\mathbb {Z} _{n_{1}\cdot n_{2}}\to \mathbb {Z} _{n_{1}}\times \mathbb {Z} _{n_{2}}$,

$f(x)=f(x{\bmod {n}}_{1},x{\bmod {n}}_{2})$

είναι ένα προς ένα.

Αφού το πεδίο ορισμού έχει $n_{1}\cdot n_{2}$ στοιχεία και το σύνολο τιμών του έχει επίσης $n_{1}\cdot n_{2}$ έπεται ότι η συνάρτηση είναι επιπλέον επί, δηλαδή κάθε σύστημα δύο εξισώσεων έχει μοναδική λύση mod $n_{1}n_{2}$.

Κατασκευαστική απόδειξη  

Αφού $n_{1},n_{2}$ είναι σχετικά πρώτοι μεταξύ τους, από την ταυτότητα Μπεζού ισχύει ότι υπάρχουν ακέραιοι $a_{1},a_{2}$ τέτοιοι ώστε

$a_{1}n_{1}+a_{2}n_{2}=1$.

Θα αποδείξουμε ότι

$x=a_{1}n_{1}m_{2}+a_{2}n_{2}m_{1}$

ικανοποιεί και τις δύο εξισώσεις.

Για την πρώτη έχουμε ότι

${\begin{aligned}x&=a_{1}n_{1}m_{2}+a_{2}n_{2}m_{1}\\&=a_{1}n_{1}m_{2}+(1-a_{1}n_{1})m_{1}\\&=(a_{1}m_{2}-a_{1}m_{1})n_{1}+m_{1}\\&\equiv m_{1}{\pmod {n_{1}}}.\end{aligned}}$

Αντίστοιχα

$x\equiv m_{2}{\pmod {n_{2}}}$.

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

Παράδειγμα 1ο

Η λύση για τις εξισώσεις

$x\equiv 2{\pmod {3}}$,

$x\equiv 3{\pmod {5}}$

είναι

$x=8+15t$ για κάθε $t\in \mathbb {Z}$.

Από τον αλγόριθμο του Ευκλείδη για τους αριθμούς $3$ και $5$ έχουμε ότι

${\begin{aligned}5&=3\cdot 1+2\\3&=2\cdot 1+1\end{aligned}}$

και επομένως

$2\cdot 3+(-1)\cdot 5=1$.

Συνεπώς, μία λύση δίνεται από

$x_{0}=2\cdot 3\cdot 3-5\cdot 1\cdot 2=8$.

Επομένως, η γενική λύση είναι

$x=8+15t$ για κάθε $t\in \mathbb {Z}$.

Παράδειγμα 2ο

Η λύση για τις εξισώσεις

$x\equiv 5{\pmod {7}}$,

$x\equiv 9{\pmod {24}}$

είναι

$x=33+168t$ για κάθε $t\in \mathbb {Z}$.

Από τον αλγόριθμο του Ευκλείδη για τους αριθμούς $7$ και $24$ έχουμε ότι

${\begin{aligned}24&=7\cdot 3+3\\7&=3\cdot 2+1\end{aligned}}$

και επομένως

$7\cdot 7+(-2)\cdot 24=1$.

Συνεπώς, μία λύση δίνεται από

$x_{0}=7\cdot 7\cdot 9+(-2)\cdot 24\cdot 5=201$.

Το $x_{0}\equiv 33{\pmod {168}}$ επομένως, η γενική λύση είναι

$x=33+168t$ για κάθε $t\in \mathbb {Z}$.

Γενίκευση για > 2 εξισώσεις

Έστω $n_{1},n_{2},\ldots ,n_{k}$ φυσικοί αριθμοί που είναι ανά δύο σχετικά πρώτοι μεταξύ τους. Τότε, για κάθε $m_{1},m_{2}$, υπάρχει $x$ ώστε

${\begin{aligned}x&\equiv m_{1}{\pmod {n_{1}}}\\x&\equiv m_{2}{\pmod {n_{2}}}\\&\vdots \\x&\equiv m_{k}{\pmod {n_{k}}}\end{aligned}}$,

και για κάθε $x_{1},x_{2}$ που ικανοποιούν αυτές τις σχέσεις ισχύει ότι

$x_{1}\equiv x_{2}{\pmod {n_{1}n_{2}\cdot \ldots \cdot n_{k}}}$.

Γενική λύση

Αφού $n_{1},n_{2}$ είναι σχετικά πρώτοι μεταξύ τους, από την ταυτότητα Μπεζού ισχύει ότι υπάρχουν ακέραιοι $a_{1},\ldots ,a_{k}$ και $b_{1},\ldots ,b_{k}$ τέτοιοι ώστε

${\textstyle a_{1}n_{1}+b_{1}{\frac {N}{n_{1}}}=1}$,

$\quad \vdots$

${\textstyle a_{k}n_{k}+b_{k}{\frac {N}{n_{k}}}=1}$,

όπου $N=n_{1}\cdot n_{2}\cdot \ldots \cdot n_{k}$. Η γενική λύση του παραπάνω συστήματος δίνεται από

${\textstyle x=b_{1}{\frac {N}{n_{1}}}m_{1}+b_{1}{\frac {N}{n_{2}}}m_{2}+\ldots +b_{k}{\frac {N}{n_{k}}}m_{k}+N\cdot t}$ για κάθε $t\in \mathbb {Z}$.

Ως ισομορφισμός

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

$f(x)=(x{\bmod {n_{1}}},x{\bmod {n_{2}}},\ldots ,x{\bmod {n_{k}}})$

είναι ισομορφισμός μεταξύ των συνόλων $\mathbb {Z} _{N}$ και $\mathbb {Z} _{n_{1}}\times \mathbb {Z} _{n_{2}}\times \ldots \times \mathbb {Z} _{n_{k}}$.

Απόδειξη

Κατασκευαστική απόδειξη  

Θα επιβεβαιώσουμε ότι το παραπάνω $x$, για κάθε $t\in \mathbb {Z}$. ικανοποιεί όλες τις ζητούμενες σχέσεις. Για ευκολία κοιτάμε την πρώτη σχέση. Χρησιμοποιώντας ότι ${\textstyle b_{1}{\frac {N}{n_{1}}}=1-a_{1}n_{1}}$ έχουμε ότι

${\textstyle {\begin{aligned}x&=b_{1}{\frac {N}{n_{1}}}m_{1}+b_{1}{\frac {N}{n_{2}}}m_{2}+\ldots +b_{k}{\frac {N}{n_{k}}}m_{k}+N\cdot t\\&=(1-a_{1}n_{1})m_{1}+b_{1}{\frac {N}{n_{2}}}m_{2}+\ldots +b_{k}{\frac {N}{n_{k}}}m_{k}+N\cdot t\\&=m_{1}-a_{1}n_{1}m_{1}+b_{1}{\frac {N}{n_{2}}}m_{2}+\ldots +b_{k}{\frac {N}{n_{k}}}m_{k}+N\cdot t\\&\equiv m_{1}{\pmod {n_{1}}},\end{aligned}}}$

καθώς ${\textstyle n_{1}\mid {\frac {N}{n_{i}}}}$ για κάθε $i\neq 1$, αφού ${\textstyle {\frac {N}{n_{i}}}=n_{1}\cdot n_{2}\cdot \ldots \cdot n_{i-1}\cdot n_{i+1}\cdot \ldots \cdot n_{k}}$.

Ομοίως αποδεικνύεται και για τις υπόλοιπες σχέσεις $i=2,3,\ldots ,k$.

Επαγωγική απόδειξη  

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

$x\equiv m_{1}{\pmod {n_{1}}}$,

$x\equiv m_{2}{\pmod {n_{2}}}$,

δηλαδή $x_{0}$ ώστε

$x_{0}=c_{0}+n_{1}n_{2}\cdot t$ για κάθε $t\in \mathbb {Z}$.

Έπειτα την λύση του συστήματος (καθώς $n_{1}n_{2}$ και $n_{3}$ είναι σχετικά πρώτοι μεταξύ τους), ´

$x\equiv c_{0}{\pmod {n_{1}n_{2}}}$,

$x\equiv m_{3}{\pmod {n_{3}}}$,

δηλαδή $x_{0}$ ώστε

$x_{1}=c_{1}+n_{1}n_{2}n_{3}\cdot t$ για κάθε $t\in \mathbb {Z}$.

Συνεχίζοντας διαδοχικά για όλα τα $n_{i}$ βρίσκουμε την λύση του συστήματος ${\bmod {n}}_{1}n_{2}\ldots n_{k}$.

Η αρχική διατύπωση του Σούνζι: x ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7) με τη λύση x = 23 + 105k, με k έναν ακέραιο αριθμό

Παράδειγμα (Το πρόβλημα του Σουανζί)

Στο πρόβλημα του Σουανζί ψάχνουμε το $x$ ώστε

$x\equiv 2{\pmod {3}}$

$x\equiv 3{\pmod {5}}$,

$x\equiv 2{\pmod {7}}$.

Αφού οι $3,5,7$ είναι σχετικά πρώτοι μεταξύ τους, χρησιμοποιώντας τον αλγόριθμο του Ευκλείδη, βρίσκουμε ότι

• Για το $3$ και το $5\cdot 7=35$

$12\cdot 3+(-1)\cdot 35=1$.

• Για το $5$ και το $3\cdot 7=21$

$(-4)\cdot 5+1\cdot 21=1$.

• Για το $7$ και το $3\cdot 5=15$

$(-2)\cdot 7+1\cdot 15=1$.

Επομένως, μία αρχική λύση είναι η

$x_{0}=(-1)\cdot 35\cdot 2+1\cdot 21\cdot 3+1\cdot 15\cdot 2=23$,

και η γενική λύση δίνεται από

$x=23+105t$ για κάθε $t\in \mathbb {Z}$.

Εφαρμογές

Επιτάχυνση πράξεων

Σε κάποιες υλοποιήσεις κρυπτογραφικών προτοκόλων, το κινεζικό θεώρημα υπολοίπων χρησιμοποιείται για την επιτάγχυνση της εκτέλεσης των πράξεων: αντί να χρησιμοποιείται ${\bmod {n}}$ χρησιμοποιούνται ${\bmod {p}}$ και ${\bmod {q}}$ για $n=pq$, και στο τέλος αντιστοιχίζεται το αποτέλεσμα.

Δείτε επίσης

• Γραμμική διοφαντική εξίσωση
• Αλγόριθμος του Ευκλείδη

Πηγές

• Dauben, Joseph W. (2007), «Chapter 3: Chinese Mathematics», στο: Katz, Victor J., επιμ., The Mathematics of Egypt, Mesopotamia, China, India and Islam : A Sourcebook, Princeton University Press, σελ. 187–384, ISBN 978-0-691-11485-9 
• Dence, Joseph B.; Dence, Thomas P. (1999), Elements of the Theory of Numbers, Academic Press, ISBN 9780122091308, https://books.google.com/books?id=YiYHw7evhjkC&pg=PA156 
• Duchet, Pierre (1995), «Hypergraphs», στο: Graham, R. L.; Grötschel, M.; Lovász, L., επιμ., Handbook of combinatorics, Vol. 1, 2, Amsterdam: Elsevier, σελ. 381–432 . See in particular Section 2.5, "Helly Property", pp. 393–394.
• Gauss, Carl Friedrich (1986), Disquisitiones Arithemeticae (Second, corrected έκδοση), New York: Springer, ISBN 978-0-387-96254-2, https://www.springer.com/mathematics/algebra/book/978-0-387-96254-2 
• Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (2nd έκδοση), Springer-Verlag, ISBN 0-387-97329-X 
• Kak, Subhash (1986), «Computational aspects of the Aryabhata algorithm», Indian Journal of History of Science 21 (1): 62–71, http://www.ece.lsu.edu/kak/AryabhataAlgorithm.pdf 
• Katz, Victor J. (1998), A History of Mathematics / An Introduction (2nd έκδοση), Addison Wesley Longman, ISBN 978-0-321-01618-8, https://archive.org/details/historyofmathema00katz 
• Libbrecht, Ulrich (1973), Chinese Mathematics in the Thirteenth Century: the "Shu-shu Chiu-chang" of Ch'in Chiu-shao, Dover Publications Inc, ISBN 978-0-486-44619-6 
• Ore, Øystein (1952), «The general Chinese remainder theorem», The American Mathematical Monthly 59 (6): 365–370, doi:10.2307/2306804 
• Ore, Oystein (1988), Number Theory and Its History, Dover, ISBN 978-0-486-65620-5, https://archive.org/details/numbertheoryitsh0000orey 
• Pisano, Leonardo (2002), Fibonacci's Liber Abaci, Springer-Verlag, σελ. 402–403, ISBN 0-387-95419-8, https://www.springer.com/mathematics/book/978-0-387-40737-1 
• Rosen, Kenneth H. (1993), Elementary Number Theory and its Applications (3rd έκδοση), Addison-Wesley, ISBN 978-0201-57889-8 
• Sengupta, Ambar N. (2012), Representing Finite Groups, A Semisimple Introduction, Springer, ISBN 978-1-4614-1232-8 
• Bourbaki, N. (1989), Algebra I, Springer, ISBN 3-540-64243-9, https://books.google.com/books?id=STS9aZ6F204C&q=%22associative+algebra%22