Čínská věta o zbytcích

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Čí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í[editovat | editovat zdroj]

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

Aritmetická formulace[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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í. 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í[editovat | editovat zdroj]

Nechť platí tvrzení "aritmetická formulace". Zobrazení f z tvrzení "algebraická formulace" je homomorfismus zřejmě. 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[editovat | editovat zdroj]

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


  1. Soustava \begin{matrix}x = a_1\ \mbox{v}\ Z_{m1} \\ x = a_2\ \mbox{v}\ Z_{m2}\end{matrix} má řešení.
  1. 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 = NSN(m1,m2), kde funkcí NSN(a,b) se rozumí nejmenší společný násobek čísel a, b.

Použití[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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*k + 4 = a
7*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*k + 4 = 1 \pmod{7}

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

5*k = 4 \pmod{7}

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

3*5*k = 3*4 \pmod{7}
15*k = 12 \pmod{7}
1*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í[editovat | editovat zdroj]

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ánky[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

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