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

Στην θεωρία αριθμών, το κινεζικό θεώρημα των υπολοίπων (γνωστό και ως CRT από τον αγγλικό όρο Chinese Remainder Theorem), αναφέρει ότι αν ξέρουμε τα υπόλοιπα $u_{1},u_{2},...,u_{k}$ ενός αριθμού $N$ με διάφορους ακεραίους $d_{1},d_{2},...,d_{k}$ , τότε μπορούμε να υπολογίσουμε το υπόλοιπο $Y$ του $N$ με το γινόμενο $D=d_{1}d_{2}\cdot \cdot \cdot d_{k}$ , αρκεί οι ακέραιοι να είναι πρώτοι μεταξύ τους.

Είναι $Y=u_{1}D_{1}x_{1}+u_{2}D_{2}x_{2}+...+u_{k}D_{k}x_{k}$ , όπου $\;\;D_{1}={\frac {D}{d_{1}}},\;\;x_{1}\;\;$ η λύση της $\;\;D_{1}x_{1}\equiv 1{\pmod {d}}_{1}$ , κ.ο.κ. και $\;\;N\equiv Y\mod D.$

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

Το θεώρημα διατυπώνεται με χρήση ισοϋπολοίπων (modulo) και ισχύει επί μίας ακέραιας περιοχής. Με το σχηματισμό ιδεωδών, μπορεί να επεκταθεί σε αντιμεταθετικούς δακτυλίους.

Ιστορία Επεξεργασία

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

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

Παράδειγμα Επεξεργασία

Το πρόβλημα του Σουανζί γράφεται ως εξής:

$N\equiv 2{\pmod {3}},\quad N\equiv 3{\pmod {5}},\quad N\equiv 2{\pmod {7}}$ , όπου οι $3,5,7$ είναι πρώτοι μεταξύ τους.

Τότε, $\quad D=3\cdot 5\cdot 7=105,\quad D_{1}={\frac {105}{3}}=35,\quad D_{2}={\frac {105}{5}}=21,\quad D_{3}={\frac {105}{7}}=15\quad$ και

$35x_{1}\equiv 1{\pmod {3}}\quad$ ή $\quad 2x_{1}\equiv 1{\pmod {3}}\quad$ ή $\quad x_{1}=2$

$21x_{2}\equiv 1{\pmod {5}}\quad$ ή $\quad x_{2}\equiv 1{\pmod {5}}\quad$ ή $\quad x_{2}=1$

$15x_{3}\equiv 1{\pmod {7}}\quad$ ή $\quad x_{3}\equiv 1{\pmod {7}}\quad$ ή $\quad x_{3}=1$ .

Έτσι, $\quad Y=2\cdot 35\cdot 2+3\cdot 21\cdot 1+2\cdot 15\cdot 1=233\quad$ και $\quad N\equiv 233{\pmod {105}}\equiv 23{\pmod {105}}=23,128,233,...$

Πράγματι, $\quad 23=3\cdot 7+2\quad$ και $\quad 23=5\cdot 4+3\quad$ και $\quad 23=7\cdot 3+2.$

Παραπομπές Επεξεργασία

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms (Second ed.), MIT Press and McGraw-Hill, ISBN 0-262-03293-7. See Section 31.5: The Chinese remainder theorem, pp. 873–876.
Ding, Cunsheng; Pei, Dingyi; Salomaa, Arto (1996), Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography, World Scientific Publishing, pp. 1–213, ISBN 981-02-2827-9
Hungerford, Thomas W. (1974), Algebra, Graduate Texts in Mathematics, Vol. 73, Springer-Verlag, pp. 131–132, ISBN 978-1-4612-6101-8
Knuth, Donald (1997), The Art of Computer Programming, Volume 2: Seminumerical Algorithms (Third ed.), Addison-Wesley, ISBN 0-201-89684-2. See Section 4.3.2 (pp. 286–291), exercise 4.6.2–3 (page 456).