Čínská věta o zbytcích

Obsah

1 Úvod
2 Znění
3 Zobecnění čínské věty
4 Příklad použití
5 Související články
6 Reference

[editovat] Úvod

Čí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, tj. oblasti nacházející se na pomezí elementární teorie čísel a algebry. Pojednává o vlastnostech čísel v okruzích kongruence modulo n (okruhy $\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 Tzu Suan Ching, kterou ve 3. století našeho letopočtu napsal čínský matematik Sun Tzu.

[editovat] Znění

Pod jménem čínská věta o zbytcích je známo více vzájemně (zcela či téměř) ekvivalentních tvrzení z algebry a teorie čísel. Následující dvě formulace jsou ekvivalentní zcela, jak bude vysvětleno níže.

[editovat] Teoreticky číselná formulace

Předpokládejme, že $m_1,m_2,\ldots,m_r$ jsou navzájem 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_k \pmod{m_r} \,\!$

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

[editovat] 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 okruhy $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)$ .

[editovat] Ekvivalence předchozích dvou formulací

Nechť platí tvrzení "teoreticky číselná 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.

[editovat] Zobecnění čínské věty

Ať m₁, m₂ jsou libovolná přirozená čísla, m_i ≥ 2 pro i = 1,2. Označme d = gcd(m₁,m₂), kde funkcí gcd(a,b) se rozumí největší společný dělitel čísel a, b. Pak jsou následující dvě podmínky ekvivalentní:

Soustava

x = a₁ v Z_m1
x = a₂ v Z_m2
má řešení.
Platí d|(a₂–a₁).

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

[editovat] Příklad použití

Máme spočíst zbytek čísla 12^{316 803} po dělení číslem 26 741, neboli v Z_{26 741}. Nejprve musíme mít daný prvočíselný rozklad čísla 26 741 = 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^{316 803} v Z_{26 741} 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^{316 803} = 12^{110·2 880+3} = 12³ = 34 v Z¹²¹
12^{316 803} = 12^{12·26 400+3} = 12³ = 12 v Z¹³
12^{316 803} = 12^{16·19 800+3} = 12³ = 11 v Z¹⁷

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

Nyní použijeme čínskou vetu o zbytcích, kde m₁ = 11², m₂ = 13 a m₃ = 17. Pak platí:
12^{316 803} = (34 ·M₁ · N₁) + (12 ·M₂ · N₂) + (11 ·M₃ · N₃) v Z_{26 741},
kde

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

N₁ = M₁^–1 = 100^–1 = 23 v Z₁₂₁
N₂ = M₂^–1 = 3^–1 = 9 v Z₁₃
N₃ = M₃^–1 = 9^–1 = 2 v Z₁₇
Tudíž 12^{316 803} = (34 · 221 · 23) + (12 · 2 057 · 9) + (11 · 1 573 · 2) = 1 728 v Z_{26 741}

Tento algoritmus výpočtu velké mocniny má své uplatnění například v šifrovacím protokolu RSA.

[editovat] Související články

Související články obsahuje
Portál Matematika

[editovat] Reference

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

Čínská věta o zbytcích v jiných jazycích: العربية, Deutsch, English, Español, Suomi, Français, עברית, Magyar, Bahasa Indonesia, Italiano, 日本語, Монгол, Nederlands, Polski, Português, Română, Русский, Simple English, Svenska, اردو, Tiếng Việt, 中文, 文言

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/%C4%8C%C3%ADnsk%C3%A1_v%C4%9Bta_o_zbytc%C3%ADch“
Stránka byla naposledy upravena v Stránka byla naposledy editována 6. 9. 2008 v 19:16.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).