Čínska zvyšková veta

Nech ${\displaystyle m_{1},m_{2},\ldots ,m_{n}}$  sú po dvoch nesúdeliteľné prirodzené čísla väčšie ako 1. Nech ${\displaystyle a_{1},a_{2},\ldots ,a_{n}}$  sú ľubovoľné celé čísla. Potom existuje riešenie x sústavy kongruencií

${\displaystyle \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 ${\displaystyle M:=m_{1}m_{2}\ldots m_{n}}$ .

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

${\displaystyle \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 ${\displaystyle k_{i}=m_{1}m_{2}\ldots m_{i-1}m_{i+1}\ldots m_{n}}$ . Čísla ${\displaystyle m_{i}}$  a ${\displaystyle k_{i}}$  sú zrejme nesúdeliteľné, čo znamená, že existujú celé čísla r,s také, že platí

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

z čoho vyplývajú kongruencie

${\displaystyle \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 ${\displaystyle m_{1},m_{2},\ldots ,m_{i-1},m_{i+1},\ldots ,m_{n}}$  deliteľmi čísla ${\displaystyle k_{i}}$ , z uvedenej sústavy dvoch kongruencií vyplýva platnosť sústavy

${\displaystyle \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 ${\displaystyle 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

${\displaystyle x:=a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n},}$ 

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

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

${\displaystyle x-x'\equiv 0\ ({\text{mod }}m_{i}).}$ 

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

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

čo bolo treba dokázať.

1. ↑ ^{a b c d} Yan, S. Y.: Number Theory for Computing. 2. vydanie, Springer, 2002.
2. ↑ Koblitz, N.: A Course in Number Theory and Cryptography. 2. vydanie, Springer-Verlag, 1994.
3. ↑ Paj's Home: Cryptography: RSA: Mathematics

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