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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Πήδηση στην πλοήγηση Πήδηση στην αναζήτηση

Το Κινεζικό Θεώρημα των Υπολοίπων (Chinese Remainder Theorem, CRT) αποτελεί μέρος της Θεωρίας Αριθμών και αναφέρει ότι αν ξέρουμε τα υπόλοιπα υ1, υ2, ..., υk ενός αριθμού N με διάφορους ακεραίους d1, d2, ..., dk, τότε μπορούμε να υπολογίσουμε το υπόλοιπο Y του Ν με το γινόμενο D = d1d2...dk, αρκεί οι ακέραιοι να είναι πρώτοι μεταξύ τους.

Είναι Y = υ1D1χ12D2χ2+...+υkDkχk, όπου D1 = D / d1, χ1 η λύση της D1χ1 = 1 (mod d1), κ.ο.κ. και

Ν = Υ (mod D).

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

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

Ιστορία[Επεξεργασία | επεξεργασία κώδικα]

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

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

Παράδειγμα[Επεξεργασία | επεξεργασία κώδικα]

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

Ν = 2 (mod 3), N = 3 (mod 5), N = 2 (mod 7), όπου οι 3, 5, 7 είναι πρώτοι μεταξύ τους.

Τότε D = 3 x 5 x 7 = 105, D1 = 105:3 = 35, D2 = 105:5 = 21, D3 = 105:7 = 15 και

35χ1 = 1 (mod 3) ή 2χ1 = 1 (mod 3) ή χ1 = 2

21χ2 = 1 (mod 5) ή 1χ2 = 1 (mod 5) ή χ2 = 1

15χ3 = 1 (mod 7) ή 1χ3 = 1 (mod 7) ή χ3 = 1.

Έτσι Y = 2 x 35 x 2 + 3 x 21 x 1 + 2 x 15 x 1 = 233 και Ν = 233 (mod 105) = 23 (mod 105) = 23, 128, 233, ...

Πράγματι 23 = 3 x 7 + 2 και 23 = 5 x 4 + 3 και 23 = 7 x 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).
Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Chinese remainder theorem της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).