Cesko.wiki Čínská věta o zbytcích
Author
Albert FloresČí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 \mathbb{Z}_n). 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í
Existují dvě ekvivalentní znění této věty:
Aritmetická formulace
Předpokládejme, že m_1,m_2,\ldots,m_r jsou navzájem po dvou nesoudělná přirozená čísla, m_i\geq2 pro i=1,\ldots,r. Potom každá soustava rovnic:
:x \equiv a_1 \pmod{m_1} \,\! :x \equiv a_2 \pmod{m_2} \,\! :\quad\quad\vdots \,\! :x \equiv a_r \pmod{m_r} \,\!
má řešení x a toto řešení je určeno jednoznačně v modulo M = m_1\cdot m_2\cdot\ldots\cdot m_r.
Algebraická formulace
Nechť m_1,m_2,\ldots,m_r jsou navzájem nesoudělná přirozená čísla, m_i\geq2 pro i=1,\ldots,r. Pak grupy Z_{m_1}\times\ldots\times Z_{m_r} a Z_{m_1\cdot\ldots\cdot m_r} jsou izomorfní. +more Izomorfismem je (kromě jiných) zobrazení f:Z_{m_1\cdot\ldots\cdot m_r}\rightarrow Z_{m_1}\times\ldots\times Z_{m_r} dané předpisem f(x)=(x \;mod\; m_1,\ldots,x\; mod \; m_r).
Ekvivalence předchozích dvou formulací
Nechť platí tvrzení "aritmetická formulace". Zobrazení f z tvrzení "algebraická formulace" je homomorfismus zřejmě. +more Dále f(x)=(a_1,\ldots,a_r) právě tehdy, když x řeší soustavu příslušnou a_1,\ldots,a_r. 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í f^{-1} 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á čísla
Ať , 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 , . +more Pak jsou následující dvě podmínky ekvivalentní: # Soustava \begin{matrix}x = a_1\ \mbox{v}\ Z_{m_1} \\ x = a_2\ \mbox{v}\ Z_{m_2}\end{matrix} má řešení. # 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 , .
Použití
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á úloha
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.
:5 \cdot k + 4 = a :7 \cdot l + 1 = a
Pro nějaká přirozená čísla k, l. Jinými slovy
:a = 4 \pmod{5} :a = 1 \pmod{7}
Proveďme substituci :5 \cdot k + 4 = 1 \pmod{7} Přičtěme trojku, abychom se zbavili čtyřky na levé straně :5 \cdot k = 4 \pmod{7} Chceme se zbavit pětky, proto rovnici vynásobme "inverzem 5", což je v tomto případě 3 :3 \cdot 5 \cdot k = 3 \cdot 4 \pmod{7} :15 \cdot k = 12 \pmod{7} :1 \cdot k = 5 \pmod{7}
Vyšlo nám, že k je 5, vojáků je tedy 5⋅5+4 = 29.
Další příklad použití
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. +more 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 větu 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
Inverze 100−1 v Z121 se najde pomocí Euklidova algoritmu:
121, 100
100, \ \ 21 \Rightarrow 21 \equiv -1 \cdot 100 \pmod{121}
\ \ 21, \ \ 16 \Rightarrow 16 = 100 - 4 \cdot 21 \equiv 5 \cdot 100 \pmod{121}
\ \ 16, \ \ \ \ 5 \Rightarrow 5 = 21 - 16 \equiv (-1 - 5) \cdot 100 = -6 \cdot 100 \pmod{121}
\ \ \ \ 5, \ \ \ \ 1 \Rightarrow 1 = 16 - 3 \cdot 5 \equiv (5 - 3 \cdot (-6)) \cdot 100 = 23 \cdot 100 \pmod{121}