Čínská věta o zbytcích

Čí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 ${\displaystyle \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 ${\displaystyle m_{1},m_{2},\ldots ,m_{r}}$ jsou navzájem po dvou nesoudělná přirozená čísla, ${\displaystyle m_{i}\geq 2}$ pro ${\displaystyle i=1,\ldots ,r}$. Potom každá soustava rovnic:

${\displaystyle x\equiv a_{1}{\pmod {m_{1}}}\,\!}$

${\displaystyle x\equiv a_{2}{\pmod {m_{2}}}\,\!}$

${\displaystyle \quad \quad \vdots \,\!}$

${\displaystyle x\equiv a_{r}{\pmod {m_{r}}}\,\!}$

má řešení x a toto řešení je určeno jednoznačně v modulo ${\displaystyle M=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{r}}$.

Algebraická formulace

Nechť ${\displaystyle m_{1},m_{2},\ldots ,m_{r}}$ jsou navzájem nesoudělná přirozená čísla, ${\displaystyle m_{i}\geq 2}$ pro ${\displaystyle i=1,\ldots ,r}$. Pak grupy ${\displaystyle Z_{m_{1}}\times \ldots \times Z_{m_{r}}}$ a ${\displaystyle Z_{m_{1}\cdot \ldots \cdot m_{r}}}$ jsou izomorfní. Izomorfismem je (kromě jiných) zobrazení ${\displaystyle f:Z_{m_{1}\cdot \ldots \cdot m_{r}}\rightarrow Z_{m_{1}}\times \ldots \times Z_{m_{r}}}$ dané předpisem ${\displaystyle 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ě. Dále ${\displaystyle f(x)=(a_{1},\ldots ,a_{r})}$ právě tehdy, když x řeší soustavu příslušnou ${\displaystyle 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í ${\displaystyle 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ť m₁, m₂ jsou libovolná přirozená čísla větší než 2. Označme d = GCD(m₁,m₂), 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 ${\displaystyle {\begin{matrix}x=a_{1}\ {\mbox{v}}\ Z_{m_{1}}\\x=a_{2}\ {\mbox{v}}\ Z_{m_{2}}\end{matrix}}}$ má řešení.
2. Platí d|(a₂–a₁) (tedy (a₂–a₁) je dělitelné d).

Jestliže platí d|(a₂–a₁), je řešení x určeno jednoznačně v Z_M, kde M = LCM(m₁,m₂), kde funkcí LCM(a,b) se rozumí nejmenší společný násobek čísel a, b.

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.

${\displaystyle 5\cdot k+4=a}$

${\displaystyle 7\cdot l+1=a}$

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

${\displaystyle a=4{\pmod {5}}}$

${\displaystyle a=1{\pmod {7}}}$

Proveďme substituci

${\displaystyle 5\cdot k+4=1{\pmod {7}}}$

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

${\displaystyle 5\cdot k=4{\pmod {7}}}$

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

${\displaystyle 3\cdot 5\cdot k=3\cdot 4{\pmod {7}}}$

${\displaystyle 15\cdot k=12{\pmod {7}}}$

${\displaystyle 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 12³¹⁶⁸⁰³ po dělení číslem 26741, neboli v Z₂₆₇₄₁. Nejprve musíme mít daný prvočíselný rozklad čísla 26741 = 11²·13·17. Protože čísla 11², 13 a 17 jsou navzájem nesoudělná, je podle čínské věty o zbytcích číslo 12³¹⁶⁸⁰³ v Z₂₆₇₄₁ určeno jednoznačně svými zbytky po dělení čísly 11², 13 a 17.

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

12³¹⁶⁸⁰³ = 12^110·2880+3 = 12³ = 34 v Z₁₂₁
12³¹⁶⁸⁰³ = 12^12·26400+3 = 12³ = 12 v Z₁₃
12³¹⁶⁸⁰³ = 12^16·19800+3 = 12³ = 11 v Z₁₇

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

Nyní použijeme čínskou větu o zbytcích, kde m₁ = 11², m₂ = 13 a m₃ = 17. Pak platí:
12³¹⁶⁸⁰³ = (34 ·M₁ · N₁) + (12 ·M₂ · N₂) + (11 ·M₃ · N₃) v Z₂₆₇₄₁,
kde

M₁ = 13 · 17 = 221
M₂ = 11² · 17 = 2057
M₃ = 11² · 13 = 1573

N₁ = M₁⁻¹ = 100⁻¹ = 23 v Z₁₂₁
N₂ = M₂⁻¹ = 3⁻¹ = 9 v Z₁₃
N₃ = M₃⁻¹ = 9⁻¹ = 2 v Z₁₇

Tudíž 12³¹⁶⁸⁰³ = (34 · 221 · 23) + (12 · 2057 · 9) + (11 · 1573 · 2) = 1728 v Z₂₆₇₄₁

Inverze 100⁻¹ v Z₁₂₁ se najde pomocí Euklidova algoritmu:
${\displaystyle 121,100}$
${\displaystyle 100,\ \ 21\Rightarrow 21\equiv -1\cdot 100{\pmod {121}}}$
${\displaystyle \ \ 21,\ \ 16\Rightarrow 16=100-4\cdot 21\equiv 5\cdot 100{\pmod {121}}}$
${\displaystyle \ \ 16,\ \ \ \ 5\Rightarrow 5=21-16\equiv (-1-5)\cdot 100=-6\cdot 100{\pmod {121}}}$
${\displaystyle \ \ \ \ 5,\ \ \ \ 1\Rightarrow 1=16-3\cdot 5\equiv (5-3\cdot (-6))\cdot 100=23\cdot 100{\pmod {121}}}$

Literatura

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

Související články

• Modulární aritmetika
• Malá Fermatova věta