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

Teória čísel
Kryptológia
Modulárna aritmetika