Ĉina restteoremo

**Ĉina restteoremo** estas la nomo de multaj similaj teoremoj de abstrakta algebro kaj nombroteorio.

## Samtempaj kongruecoj de entjeroj 
Samtempa kongrueco de entjeroj estas sistemo de linearaj kongruecoj

: 
\begin{matrix}
x & \equiv & a_1 & \pmod{m_1} \\
x & \equiv & a_2 & \pmod{m_2} \\
  & \vdots &     &            \\
x & \equiv & a_n & \pmod{m_n} \\
\end{matrix}

por kiu estas trovendaj ĉiuj x, kiuj solvas ĉiujn kongruecojn samtempe. Se solvo x ekzistas kaj oni difinas M := \operatorname{pmko} \{ m_1, m_2, \ldots, m_n \} ("pmko" signifas la plej malgrandan komunan oblon), la aro \{ x + k \cdot M \mid k \in \mathbb{Z} \} enhavas ĉiujn solvojn. Sed ankaŭ eblas, ke neniu solvo ekzistas.

### Reciproke primaj moduloj 
La origina versio de la restteoremo (el la libro *La kompendio de aritmetiko de Sūn Zǐ* de la ĉina matematikisto Sūn Zǐ) deklaras eldiron pri samtempaj kongruecoj en la kazo, ke la moduloj estas reciproke primaj. Ĝi tekstas:

m_1, m_2, \ldots, m_n estu popare reciproke primaj entjeroj. Tiam por ĉiu entjera opo a_1, a_2, \ldots, a_n ekzistas entjero x, kiu solvas la jenan samtempan kongruecon:
: x \equiv a_i \pmod{m_i} kun i = 1, 2, \ldots, n
Ĉiuj solvoj por tiu kongrueco estas kongrua module M := m_1 \cdot m_2 \cdot \ldots \cdot m_n.

Tiu produto M egalas al la PMKO kaŭze de reciproka primeco.

**Trovado de unu solvo**

Unu solvo x povas esti trovita jene: Por ĉiu i la nombroj m_i kaj M_i := \tfrac{M}{m_i} estas reciproke primaj, do oni povas trovi du nombrojn r_i kaj s_i, ekzemple kun la etendita eŭklida algoritmo, kun la propreco
: r_i \cdot m_i + s_i \cdot M_i = 1.

Se oni metas e_i := s_i \cdot M_i, tiam validas
: e_i \equiv 1 \pmod{m_i}
: e_i \equiv 0 \pmod{m_j}, \ j \neq i.

Tiam la nombro
: x := \sum_{i=1}^n a_i e_i
estas solvo por la samtempa kongrueco.

**Ekzemplo**

Estu serĉata entjero x, por kiu validas jeno:
: 
\begin{matrix}
x & \equiv & 2 \pmod{3} \\
x & \equiv & 3 \pmod{4} \\
x & \equiv & 2 \pmod{5} \\
\end{matrix}

Ĉi tie validas M = 3 \cdot 4 \cdot 5 = 60, \ M_1 = \tfrac{M}{3} = 20, \ M_2 = \tfrac{M}{4} = 15, \ M_3 = \tfrac{M}{5} = 12.
Kun helpo de etendita eŭklida algoritmo oni kalkulas
: 7 \cdot 3 + (-1) \cdot 20 = 1, do e_1 = -20
: 4 \cdot 4 + (-1) \cdot 15  = 1, do e_2 = -15
:  5 \cdot 5 + (-2) \cdot 12 = 1, do e_3 = -24

Tiam unu solvo estas x = 2 \cdot (-20) + 3 \cdot (-15) + 2 \cdot (-24) = -133. Kaŭze de -133 \equiv 47 \pmod{60} ĉiuj aliaj solvoj estas kongruaj al 47 module 60.

### Ĝenerala kazo 
Ankaŭ ĉe la kazo, ke la moduloj ne estas reciproke primaj, ekzistas solvo kelkfoje. La ekzakta kondiĉo tekstas: Solvo por la samtempa kongrueco ekzistas strikte tiam, se por ĉiuj i \neq j validas:
: a_i \equiv a_j \pmod{\operatorname{pgkd}(m_i, m_j)}.
Ĉiuj solvoj estas kongruaj module la PMKO de m_i.

En la kazo, ke solvo ekzistas, unu samtempa kongrueco povas esti solvita, ekzemple, per substituoj, paŝo post paŝo, ankaŭ se la moduloj ne estas reciproke primaj.

**Ekzemplo**

La celo de unu klasika enigmo estas trovi la malplej grandan naturan nombron, kiu havas la reston 1 ĉe dividado kun resto per 2, 3, 4, 5 kaj 6, kaj estas nete dividebla per 7. Do oni serĉas la malplej grandan pozitivan solvon x de la samtempa kongrueco.
: 
\begin{matrix}
x & \equiv & 1 & \pmod{2} \\
x & \equiv & 1 & \pmod{3} \\
x & \equiv & 1 & \pmod{4} \\
x & \equiv & 1 & \pmod{5} \\
x & \equiv & 1 & \pmod{6} \\
x & \equiv & 0 & \pmod{7} \\
\end{matrix}

Ĉar la moduloj ne estas reciproke primaj, oni ne povas apliki la ĉinan restteoremon senpere. Sed oni povas kunigi la unuan kvin kondiĉojn al x \equiv 1 \pmod{\operatorname{pmko} \{ 2, 3, 4, 5, 6 \}}, kiu signifas, ke solvo estu trovita por
: 
\begin{matrix}
x & \equiv & 1 & \pmod{60} \\
x & \equiv & 0 & \pmod{7} \\
\end{matrix}

Tiu sistemo de kongruecoj nun solveblas pere de la ĉina restteoremo.

## Rekta solvado de samtempaj kongruecoj de entjeroj 
La jenaj ambaŭ kongruecoj estu donita:
: 
\begin{matrix}
x & \equiv & a & \pmod{n} \\
x & \equiv & b & \pmod{m} \\
\end{matrix}

Se tiuj solveblas, do a \equiv b \pmod d, ili estas ekvivalenta je la simpla kongrueco:
: 
\begin{matrix}
x & \equiv & a - yn \frac{a-b}{d} & \pmod{ \frac{nm}{d}} \\
\end{matrix}

kun d = \operatorname{pgkd}(n,m) = yn + zm.

Tio funkcias ankaŭ kiam la nombroj n kaj m ne estas reciproke primaj; tio do estas klara simpligo por solvi samtempajn kongruecojn. Sistemo de kongruecoj povas esti solvita per refarita aplikado de tiu simpligo.

Kategorio:Matematiko
Kategorio:Teoremoj