Čínska zvyšková veta

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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

Znenie vety[1][upraviť | upraviť zdroj]

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[1][upraviť | upraviť zdroj]

Existencia[upraviť | upraviť zdroj]

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 [upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

  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

Externé odkazy[upraviť | upraviť zdroj]