Theorem (čínská zbytková). Mějme soustavu

k

rovnic ve tvaru

x \equiv r_i \pmod{m_i}

, kde jednotlivá

m_i

jsou po dvou nesoudělná. Tato soustava má řešení a pro každé řešení platí

x \equiv \sum_i c_i \frac{m}{m_i} r_i \pmod{m}

. kde

m = \prod_i m_i

a

c_i \frac{m}{m_i} \equiv 1 \pmod{m_i}

.

Exercise. Řešme soustavu rovnic

\begin{align*}x &\equiv 2 \pmod{3} \\ x &\equiv 1 \pmod{5} \\ x &\equiv 6 \pmod{7} \\\end{align*}

Máme

m = 3 \cdot 5 \cdot 7 = 105

. Má platit

x \equiv c_1 \cdot 5 \cdot 7 \cdot 2 + c_2 \cdot 3 \cdot 7 \cdot 1 + c_3 \cdot 3 \cdot 5 \cdot 6 \pmod{105} \land c_1 \cdot 5 \cdot 7 \equiv 1 \pmod{3} \land c_2 \cdot 3 \cdot 7 \equiv 1 \pmod{5} \land c_3 \cdot 3 \cdot 5 \equiv 1 \pmod{7}

.

Proof.

(existence) Mějme $x = \sum_i c_i \frac{m}{m_i} r_i$ . Pro každé $i$ potom platí, že všechny sčítance kromě $i$ -tého jsou dělitelné $m_i$ a podle podmínky pro ten $i$ -tý platí $x \equiv r_i \pmod{m_i}$ , tedy původní soustava rovnic je vyřešena.

(všechna řešení) $(\forall i: z \equiv x \pmod{m_i}) \iff z \equiv x \pmod{m}$ .

Theorem. Soustava

x \equiv r_1 \pmod{m_1}, x \equiv r_2 \pmod{m_2}

má řešení právě tehdy, pokud

\gcd(m_1, m_2) \mid r_2 - r_1

.

Čínská zbytková věta