Čínska zvyšková veta

Čínska zvyšková veta alebo čínska veta o zvyškoch je veta v teórii čísel objavená čínskym matematikom Sun-c' hovoriaca o riešeniach systémov lineárnych kongruencií. Medzi hlavné aplikácie vety patrí dôkaz bezpečnosti šifrovacieho algoritmu RSA.

Znenie vety

Nech $m_1, m_2, \ldots, m_n$ sú po dvoch nesúdeliteľné prirodzené čísla väčšie ako 1. Nech $a_1, a_2, \ldots, a_n$ sú ľubovoľné celé čísla. Potom existuje riešenie x sústavy kongruencií

$\left.\begin{array}{ccl}x & \equiv & a_1\ (\text{mod } m_1) \\ x & \equiv & a_2\ (\text{mod } m_2) \\ \vdots & \vdots & \vdots \\ x & \equiv & a_n\ (\text{mod } m_{n}) \end{array}\right\},$

pričom všetky takéto riešenia x sú navzájom kongruentné modulo $M := m_1 m_2 \ldots m_n$.

Dôkaz

Existencia

Vyriešime najprv špeciálny prípad uvedenej sústavy kongruencií:

$\left.\begin{array}{ccl}x & \equiv & 0\ (\text{mod } m_1) \\ \vdots & \vdots & \vdots \\ x & \equiv & 0\ (\text{mod } m_{i-1}) \\ x & \equiv & 1\ (\text{mod } m_{i}) \\ x & \equiv & 0\ (\text{mod } m_{i+1}) \\ \vdots & \vdots & \vdots \\ x & \equiv & 0\ (\text{mod } m_n) \\ \end{array}\right\}.$

Nech $k_i = m_1 m_2 \ldots m_{i-1} m_{i+1} \ldots m_n$. Čísla $m_i$ a $k_i$ sú zrejme nesúdeliteľné, čo znamená, že existujú celé čísla r,s také, že platí

$r k_i + s m_i = 1 \! ,$

z čoho vyplývajú kongruencie

$\left.\begin{array}{ccl}r k_i & \equiv & 0\ (\text{mod } k_i) \\ r k_i & \equiv & 1\ (\text{mod } m_i) \end{array}\right\}.$

Keďže sú ale všetky čísla $m_1, m_2, \ldots, m_{i-1}, m_{i+1}, \ldots, m_n$ deliteľmi čísla $k_i$, z uvedenej sústavy dvoch kongruencií vyplýva platnosť sústavy

$\left.\begin{array}{ccl}r k_i & \equiv & 0\ (\text{mod } m_1) \\ \vdots & \vdots & \vdots \\ r k_i & \equiv & 0\ (\text{mod } m_{i-1}) \\ r k_i & \equiv & 1\ (\text{mod } m_{i}) \\ r k_i & \equiv & 0\ (\text{mod } m_{i+1}) \\ \vdots & \vdots & \vdots \\ r k_i & \equiv & 0\ (\text{mod } m_n) \\ \end{array}\right\},$

čo znamená, že hodnota $x_i := r k_i$ je riešením uvedeného špeciálneho prípadu systému kongruencií. Z toho už ale triviálnou úvahou vyplýva, že riešenie všeobecného systému kongruencií má tvar

$x := a_1 x_1 + a_2 x_2 + \ldots + a_n x_n,$

čo znamená, že existencia riešenia je dokázaná.

Jednoznačnosť modulo $M$

Nech $x, x'$ sú riešenia uvedenej sústavy kongruencií. Z toho vyplýva, že pre každé i platí

$x - x' \equiv 0\ (\text{mod } m_i).$

Inými slovami, hodnota $m_i$ delí $x - x'$ pre každé i. Z toho vyplýva, že aj najmenší spoločný násobok čísel $m_1, \ldots, m_n$ delí $x - x'$. Ale keďže sú čísla $m_1, \ldots, m_n$ po dvoch nesúdeliteľné, má tento najmenší spoločný násobok hodnotu M, čo znamená, že

$x \equiv x'\ (\text{mod } M),$

čo bolo treba dokázať.

Externé odkazy

• Čínska veta o zvyškoch - Wolfram MathWorld (po anglicky).
• Čínska veta o zvyškoch - Cut-The-Knot (po anglicky).