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