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

Στην θεωρία αριθμών, το κινεζικό θεώρημα των υπολοίπων (γνωστό και ως θεώρημα υπολοίπων του Νικόμαχου), αναφέρει ότι αν γνωρίζουμε τα υπόλοιπα  ενός ακεραίου  με τους ακεραίους  που είναι σχετικά πρώτοι μεταξύ τους, τότε μπορούμε να υπολογίσουμε το υπόλοιπο του  με το γινόμενό τους .< Επίσης δίνει και έναν αποδοτικό τρόπο υπολογισμού του βασισμένο στον αλγόριθμο του Ευκλείδη.

Για παράδειγμα, αν γνωρίζουμε ότι
 και ,
τότε (όπως θα δούμε παρακάτω) προκύπτει ότι
.
Αυτό μπορεί να επαληθευφθεί και από τον παρακάτω πίνακα υπολοίπων
{| class="wikitable"
| || 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14
|-
| Υπόλοιπο με το  || 0 || 1 || 2 || 0 || 1 || 2 || 0 || 1 || 2 || 0 || 1 || 2 || 0 || 1 || 2 
|-
| Υπόλοιπο με το  || 0 || 1 || 2 || 3 || 4 || 0 || 1 || 2 || 3 || 4 || 0 || 1 || 2 || 3 || 4
|}

Πιο γενικά, αν γνωρίζουμε τα υπόλοιπα  ενός ακεραίου  με διάφορους ακεραίους , τότε μπορούμε να υπολογίσουμε το υπόλοιπο του  με το γινόμενο  , αρκεί οι ακέραιοι να είναι σχετικά πρώτοι μεταξύ τους.

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

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

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

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

 Διατύπωση 

Έστω  και  δύο φυσικοί αριθμοί σχετικά πρώτοι μεταξύ τους. Τότε, για κάθε , υπάρχει  ώστε 
, και 
,
και για κάθε  που ικανοποιούν αυτές τις σχέσεις ισχύει ότι 
.

 Γενική λύση 
Αφού  είναι σχετικά πρώτοι μεταξύ τους, από την ταυτότητα Μπεζού ισχύει ότι υπάρχουν ακέραιοι  τέτοιοι ώστε 
.
Η γενική λύση του παραπάνω συστήματος δίνεται από 
 για κάθε . 
 Ως ισομορφισμός 
Το θεώρημα μπορεί να διατυπωθεί και ως ισομορφισμός μεταξύ δύο συνόλων. Έστω  και  δύο φυσικοί αριθμοί σχετικά πρώτοι μεταξύ τους. Τότε, η συνάρτηση

είναι ισομορφισμός μεταξύ των συνόλων  και .

 Αποδείξεις 

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

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

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

είναι 
 για κάθε .

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

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

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

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

είναι 
 για κάθε .

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

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

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

Έστω  φυσικοί αριθμοί που είναι ανά δύο σχετικά πρώτοι μεταξύ τους. Τότε, για κάθε , υπάρχει  ώστε 
,
και για κάθε  που ικανοποιούν αυτές τις σχέσεις ισχύει ότι 
.

 Γενική λύση 
Αφού  είναι σχετικά πρώτοι μεταξύ τους, από την ταυτότητα Μπεζού ισχύει ότι υπάρχουν ακέραιοι  και  τέτοιοι ώστε 
,

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

είναι ισομορφισμός μεταξύ των συνόλων  και .

 Απόδειξη 

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

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

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

 Εφαρμογές 

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

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

 Παραπομπές 

Πηγές

. See in particular Section 2.5, "Helly Property", pp. 393–394.



Κατηγορία:Θεωρία αριθμών