Čínská zbytková věta

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

k

rovnic ve tvaru

x \equiv r_{i} (m o d 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} (m o d m)

. kde

m = \prod_{i} m_{i}

c_{i} \frac{m}{m_{i}} \equiv 1 (m o d m_{i})

Cvičení. Řešme soustavu rovnic

\begin{aligned} x & \equiv 2 (m o d 3) \\ x & \equiv 1 (m o d 5) \\ x & \equiv 6 (m o d 7) \end{aligned}

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 (m o d 105) \land c_{1} \cdot 5 \cdot 7 \equiv 1 (m o d 3) \land c_{2} \cdot 3 \cdot 7 \equiv 1 (m o d 5) \land c_{3} \cdot 3 \cdot 5 \equiv 1 (m o d 7)

Důkaz.

(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} (m o d m_{i})$ , tedy původní soustava rovnic je vyřešena.

(všechna řešení) $(\forall i : z \equiv x (m o d m_{i})) ⟺ z \equiv x (m o d m)$ .

Věta. Soustava

x \equiv r_{1} (m o d m_{1}), x \equiv r_{2} (m o d m_{2})

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

\gcd (m_{1}, m_{2}) | r_{2} - r_{1}