Čínska zvyšková veta alebo čínska veta o zvyškoch je veta v teórii čísel objavená čínskym matematikom Sun-c' Yan, S. Y.: Number Theory for Computing. 2. vydanie, Springer, 2002. hovoriaca o riešeniach systémov lineárnych kongruencií.Koblitz, N.: A Course in Number Theory and Cryptography. 2. vydanie, Springer-Verlag, 1994. Medzi hlavné aplikácie vety patrí dôkaz bezpečnosti šifrovacieho algoritmu RSA.Paj's Home: Cryptography: RSA: Mathematics
Znenie vety
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í
pričom všetky takéto riešenia x sú navzájom kongruentné modulo .
Dôkaz
Existencia
Vyriešime najprv špeciálny prípad uvedenej sústavy kongruencií:
Nech . Čísla a sú zrejme nesúdeliteľné, čo znamená, že existujú celé čísla r,s také, že platí
z čoho vyplývajú kongruencie
Keďže sú ale všetky čísla deliteľmi čísla , z uvedenej sústavy dvoch kongruencií vyplýva platnosť sústavy
č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
čo znamená, že existencia riešenia je dokázaná.
Jednoznačnosť modulo
Nech sú riešenia uvedenej sústavy kongruencií. Z toho vyplýva, že pre každé i platí
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
čo bolo treba dokázať.
Referencie
Externé odkazy
Čínska veta o zvyškoch - Wolfram MathWorld . Čínska veta o zvyškoch - Cut-The-Knot .
Kategória:Teória čísel Kategória:Kryptológia Kategória:Modulárna aritmetika