Čí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í

$rk_{i}+sm_{i}=1\!,$

z čoho vyplývajú kongruencie

$\left.{\begin{array}{ccl}rk_{i}&\equiv &0\ ({\text{mod }}k_{i})\\rk_{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}rk_{i}&\equiv &0\ ({\text{mod }}m_{1})\\\vdots &\vdots &\vdots \\rk_{i}&\equiv &0\ ({\text{mod }}m_{i-1})\\rk_{i}&\equiv &1\ ({\text{mod }}m_{i})\\rk_{i}&\equiv &0\ ({\text{mod }}m_{i+1})\\\vdots &\vdots &\vdots \\rk_{i}&\equiv &0\ ({\text{mod }}m_{n})\\\end{array}}\right\},$

čo znamená, že hodnota $x_{i}:=rk_{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).