Čí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, 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.

Obsah

[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ť m1, m2 jsou libovolná přirozená čísla, mi ≥ 2 pro i = 1,2. Označme d = gcd(m1,m2), 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í:

  1. Soustava

    x = a1 v Zm1
    x = a2 v Zm2
    má řešení.

  2. Platí d|(a2–a1).

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 a, b.

[editovat] Příklad použití

Máme spočíst zbytek čísla 12316 803 po dělení číslem 26 741, neboli v Z26 741. Nejprve musíme mít daný prvočíselný rozklad čísla 26 741 = 112·13·17. Protože čísla 112, 13 a 17 jsou navzájem nesoudělná, je podle čínské věty o zbytcích číslo 12316 803 v Z26 741 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:

12316 803 = 12110·2 880+3 = 123 = 34 v Z121
12316 803 = 1212·26 400+3 = 123 = 12 v Z13
12316 803 = 1216·19 800+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í:
12316 803 = (34 ·M1 · N1) + (12 ·M2 · N2) + (11 ·M3 · N3) v Z26 741,
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íž 12316 803 = (34 · 221 · 23) + (12 · 2 057 · 9) + (11 · 1 573 · 2) = 1 728 v Z26 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
Citováno z „http://cs.wikipedia.org/wiki/%C4%8C%C3%ADnsk%C3%A1_v%C4%9Bta_o_zbytc%C3%ADch“