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

Στην θεωρία αριθμών, το **κινεζικό θεώρημα των υπολοίπων** (γνωστό και ως **θεώρημα υπολοίπων του Νικόμαχου**), αναφέρει ότι αν γνωρίζουμε τα υπόλοιπα 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}.
Αυτό μπορεί να επαληθευφθεί και από τον παρακάτω πίνακα υπολοίπων
::

Πιο γενικά, αν γνωρίζουμε τα υπόλοιπα m_1, m_2, \ldots , m_k ενός ακεραίου x με διάφορους ακεραίους n_1, n_2, \ldots, n_k, τότε μπορούμε να υπολογίσουμε το υπόλοιπο του x με το γινόμενο  n_1n_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_1n_1 + a_2n_2 = 1.
Η γενική λύση του παραπάνω συστήματος δίνεται από 
:x = a_1n_1 m_2 + a_2n_2 m_1 + n_1n_2 \cdot t για κάθε t \in \Z. 
### Ως ισομορφισμός
Το θεώρημα μπορεί να διατυπωθεί και ως ισομορφισμός μεταξύ δύο συνόλων. Έστω n_1 και n_2 δύο φυσικοί αριθμοί σχετικά πρώτοι μεταξύ τους. Τότε, η συνάρτηση
:f(x) = (x \bmod{n_1}, x \bmod{n_2}) 
είναι ισομορφισμός μεταξύ των συνόλων \Z_{n_1 \cdot n_2} και \Z_{n_1} \times \Z_{n_2}.

## Αποδείξεις

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

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

Η λύση για τις εξισώσεις 
:x \equiv 2 \pmod{3},
:x \equiv 3 \pmod{5} 
είναι 
:x = 8 + 15t για κάθε t \in \Z.

Από τον αλγόριθμο του Ευκλείδη για τους αριθμούς 3 και 5 έχουμε ότι 
:
\begin{align} 
5 & = 3 \cdot 1 + 2 \\
3 & = 2 \cdot 1 + 1 
\end{align}

και επομένως 
: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 \Z.

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

Η λύση για τις εξισώσεις 
:x \equiv 5 \pmod{7},
:x \equiv 9 \pmod{24} 
είναι 
:x = 33 + 168t για κάθε t \in \Z.

Από τον αλγόριθμο του Ευκλείδη για τους αριθμούς 7 και 24 έχουμε ότι 
:
\begin{align} 
24 & = 7 \cdot 3 + 3 \\
7 & = 3 \cdot 2 + 1 
\end{align}

και επομένως 
: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 \Z.

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

Έστω n_1, n_2, \ldots, n_k φυσικοί αριθμοί που είναι ανά δύο σχετικά πρώτοι μεταξύ τους. Τότε, για κάθε m_1, m_2, υπάρχει x ώστε 
:\begin{align}
x & \equiv m_1 \pmod{n_1} \\
x & \equiv m_2 \pmod{n_2} \\
 & \vdots \\
x & \equiv m_k \pmod{n_k}
\end{align},
και για κάθε 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 τέτοιοι ώστε 
:a_1n_1 + b_1 \frac{N}{n_1} = 1,
:\quad \vdots
:a_kn_k + b_k \frac{N}{n_k} = 1,
όπου N = n_1 \cdot n_2 \cdot \ldots \cdot n_k.
Η γενική λύση του παραπάνω συστήματος δίνεται από 
: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 \Z. 
### Ως ισομορφισμός
Το θεώρημα μπορεί να διατυπωθεί και ως ισομορφισμός μεταξύ δύο συνόλων. Έστω n_1 και n_2 δύο φυσικοί αριθμοί σχετικά πρώτοι μεταξύ τους. Τότε, η συνάρτηση
:f(x) = (x \bmod{n_1}, x \bmod{n_2}, \ldots , x \bmod{n_k}) 
είναι ισομορφισμός μεταξύ των συνόλων \Z_{N} και \Z_{n_1} \times \Z_{n_2} \times \ldots \times \Z_{n_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 \Z.

## Εφαρμογές

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

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

## Παραπομπές

## Πηγές
*
*
*. See in particular Section 2.5, "Helly Property", pp.&nbsp;393–394.
* 
* 
*
*
*
*
*
*
*
*
*

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