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

$x\equiv a_1(\mathrm{mod}{m}_1)$

$x\equiv a_2(\mathrm{mod}{m}_2)$

$⋮$

$x\equiv a_r(\mathrm{mod}{m}_r)$

má řešení x a toto řešení je určeno jednoznačně v modulo $M=m_1\cdot m_2\cdot \dots \cdot m_r$.

Algebraická formulace

Nechť $m_1,m_2,\dots ,m_r$ jsou navzájem nesoudělná přirozená čísla, $m_i\ge 2$ pro $i=1,\dots ,r$. Pak grupy $Z_{m_1}\times \dots \times Z_{m_r}$ a $Z_{m_1\cdot \dots \cdot m_r}$ jsou izomorfní. Izomorfismem je (kromě jiných) zobrazení $f:Z_{m_1\cdot \dots \cdot m_r}\to Z_{m_1}\times \dots \times Z_{m_r}$ dané předpisem $f(x)=(xmod{m}_1,\dots ,xmod{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 $f(x)=(a_1,\dots ,a_r)$ právě tehdy, když x řeší soustavu příslušnou $a_1,\dots ,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ť Šablona:Var, Šablona:Var 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 Šablona:Var, Šablona:Var. Pak jsou následující dvě podmínky ekvivalentní:

1. Soustava $\begin{array}{c}x=a_1\text{v}{Z}_{m_1}\\ x=a_2\text{v}{Z}_{m_2}\end{array}$ má řešení.
2. Platí d|(a₂–a₁) (tedy (a₂–a₁) je dělitelné d).

Jestliže platí d|(a₂–a₁), je řešení Šablona:Var 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 Šablona:Var, Šablona:Var.

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(\mathrm{mod}5)$

$a=1(\mathrm{mod}7)$

Proveďme substituci

$5\cdot k+4=1(\mathrm{mod}7)$

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

$5\cdot k=4(\mathrm{mod}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(\mathrm{mod}7)$

$15\cdot k=12(\mathrm{mod}7)$

$1\cdot k=5(\mathrm{mod}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:
$121,100$
$100,21\Rightarrow 21\equiv -1\cdot 100(\mathrm{mod}121)$
$21,16\Rightarrow 16=100-4\cdot 21\equiv 5\cdot 100(\mathrm{mod}121)$
$16,5\Rightarrow 5=21-16\equiv (-1-5)\cdot 100=-6\cdot 100(\mathrm{mod}121)$
$5,1\Rightarrow 1=16-3\cdot 5\equiv (5-3\cdot (-6))\cdot 100=23\cdot 100(\mathrm{mod}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