Čínska zvyšková veta alebo čínska veta o zvyškoch je veta v teórii čísel objavená čínskym matematikom Sun-c' [1] hovoriaca o riešeniach systémov lineárnych kongruencií.[1][2] Medzi hlavné aplikácie vety patrí dôkaz bezpečnosti šifrovacieho algoritmu RSA.[3]
Nech
sú po dvoch nesúdeliteľné prirodzené čísla väčšie ako 1. Nech
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\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/abe4f5ff413b570d5a05b48a2ee36eeb1a4f6051)
pričom všetky takéto riešenia x sú navzájom kongruentné modulo
.
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\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4863f13d2450af5717e0d6bf834a1357044357c6)
Nech
. Čísla
a
sú zrejme nesúdeliteľné, čo znamená, že existujú celé čísla r,s také, že platí
![{\displaystyle rk_{i}+sm_{i}=1\!,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d84a6fe914597a974942ae177c2485ac64cbd126)
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\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/033618b0bb254a4c9832c785fa5daf1d7b0e8936)
Keďže sú ale všetky čísla
deliteľmi čísla
, 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\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/79d68f6e618643c62ee248b9c3f1b2c1ba86534d)
čo znamená, že hodnota
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},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e1b64543111d4604919b156190bb42e58f88d11)
čo znamená, že existencia riešenia je dokázaná.
Jednoznačnosť modulo
[upraviť | upraviť zdroj]
Nech
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}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1d6b8175a341c4cc78b6ed901ab187f448a82e9)
Inými slovami, hodnota
delí
pre každé i. Z toho vyplýva, že aj najmenší spoločný násobok čísel
delí
. Ale keďže sú čísla
po dvoch nesúdeliteľné, má tento najmenší spoločný násobok hodnotu M, čo znamená, že
![{\displaystyle x\equiv x'\ ({\text{mod }}M),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae970df38c1ae42a2c846b7f953e7dee5cd01c04)
čo bolo treba dokázať.
- ↑ a b c d Yan, S. Y.: Number Theory for Computing. 2. vydanie, Springer, 2002.
- ↑ Koblitz, N.: A Course in Number Theory and Cryptography. 2. vydanie, Springer-Verlag, 1994.
- ↑ Paj's Home: Cryptography: RSA: Mathematics