Čínská věta o zbytcích

matematické tvrzení z modulární aritmetiky

Čínská věta o zbytcích (také známa jako Čínská věta o zbytku nebo Čínská zbytková věta) je matematické tvrzení z modulární aritmetiky. Pojednává o vlastnostech čísel v grupách kongruence modulo n (grupy ). Využívá se v algoritmech pro zpracování velkých čísel nebo v kryptografii. Nejstarší zmínkou o této větě je problém 26 z knihy Sun-c' Suan Ťing, kterou ve 3. století našeho letopočtu napsal čínský matematik Sun-c'.

ZněníEditovat

Existují dvě ekvivalentní znění této věty:

Aritmetická formulaceEditovat

Předpokládejme, že   jsou navzájem po dvou nesoudělná přirozená čísla,   pro  . Potom každá soustava rovnic:

 
 
 
 

má řešení x a toto řešení je určeno jednoznačně v modulo  .

Algebraická formulaceEditovat

Nechť   jsou navzájem nesoudělná přirozená čísla,   pro  . Pak grupy   a   jsou izomorfní. Izomorfismem je (kromě jiných) zobrazení   dané předpisem  .

Ekvivalence předchozích dvou formulacíEditovat

Nechť platí tvrzení "aritmetická formulace". Zobrazení f z tvrzení "algebraická formulace" je homomorfismus zřejmě. Dále   právě tehdy, když x řeší soustavu příslušnou  . Proto f je prosté díky jednoznačnosti řešení a f je na díky existenci řešení.

Nechť naopak platí „algebraická formulace“, pak zobrazení   poskytuje řešení soustavy z „teoreticky číselné formulace“. Jednoznačnost tohoto řešení plyne z prostoty f.

Zobecnění čínské věty pro soudělná číslaEditovat

Ať m1, m2 jsou libovolná přirozená čísla větší než 2. Označme d = GCD(m1,m2), kde GCD(a,b) se rozumí největší společný dělitel čísel a, b. Pak jsou následující dvě podmínky ekvivalentní:

  1. Soustava   má řešení.
  2. Platí d|(a2–a1) (tedy (a2–a1) je dělitelné d).

Jestliže platí d|(a2–a1), je řešení určeno jednoznačně v ZM, kde M = LCM(m1,m2), kde funkcí LCM(a,b) se rozumí nejmenší společný násobek čísel a, b.

PoužitíEditovat

Na základě této věty lze vytvořit algoritmus výpočtu zbytku po dělení velké mocniny zadaného čísla. Tento algoritmus má své uplatnění například v šifrovacím protokolu RSA.

Praktická úlohaEditovat

Pokud vojáky seřadíme do 5 řad, zbudou 4. Pokud je seřadíme do 7 řad, zbude 1. Kolik je vojáků?

Čínská věta říká, že v rozmezí 1 až 35 je právě jedno číslo, které vyhovuje našemu zadání. Řekněme, že vojáků je a. Zapišme problém matematicky.

 
 

Pro nějaká přirozená čísla k, l. Jinými slovy

 
 

Proveďme substituci

 

Přičtěme trojku, abychom se zbavili čtyřky na levé straně

 

Chceme se zbavit pětky, proto rovnici vynásobme "inverzem 5", což je v tomto případě 3

 
 
 

Vyšlo nám, že k je 5, vojáků je tedy 5*5+4 = 29.

Další příklad použitíEditovat

Máme spočíst zbytek čísla 12316803 po dělení číslem 26741, neboli v Z26741. Nejprve musíme mít daný prvočíselný rozklad čísla 26741 = 112·13·17. Protože čísla 112, 13 a 17 jsou navzájem nesoudělná, je podle čínské věty o zbytcích číslo 12316803 v Z26741 určeno jednoznačně svými zbytky po dělení čísly 112, 13 a 17.

Následně využijeme faktu, že aφ(m) = 1 v Zm (Eulerova funkce) a spočteme tyto zbytky:

12316803 = 12110·2880+3 = 123 = 34 v Z121
12316803 = 1212·26400+3 = 123 = 12 v Z13
12316803 = 1216·19800+3 = 123 = 11 v Z17

(protože φ(112) = 110 ,φ(13) = 12 ,φ(17) = 16)

Nyní použijeme čínskou vetu o zbytcích, kde m1 = 112, m2 = 13 a m3 = 17. Pak platí:
12316803 = (34 ·M1 · N1) + (12 ·M2 · N2) + (11 ·M3 · N3) v Z26741,
kde

M1 = 13 · 17 = 221
M2 = 112 · 17 = 2057
M3 = 112 · 13 = 1573

N1 = M1–1 = 100–1 = 23 v Z121
N2 = M2–1 = 3–1 = 9 v Z13
N3 = M3–1 = 9–1 = 2 v Z17
Tudíž 12316803 = (34 · 221 · 23) + (12 · 2057 · 9) + (11 · 1573 · 2) = 1728 v Z26741

Související článkyEditovat

ReferenceEditovat

  • RNDr. Jiří Velebil, Ph.D.: Diskrétní matematika a logika, ČVUT Praha 2006