Čínská věta o zbytcích: Porovnání verzí

'''Čínská věta o zbytcích''' (také známa jako '''Čínská věta o zbytku''' nebo '''Čínská zbytková věta''') je [[matematika|matematické]] [[tvrzení (matematika)|tvrzení]] z [[modulární aritmetika|modulární aritmetiky]]. Pojednává o vlastnostech čísel v [[Grupa|grupách]] [[kongruence modulo n]] (grupy <math>\mathbb{Z}_n</math>). Využívá se v algoritmech pro zpracování velkých čísel nebo v [[kryptografie|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 [[Čína|čínský]] [[matematik]] [[Sun-c' (matematik)|Sun-c']].

 

== Zobecnění čínské věty pro soudělná čísla ==

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

 

# Soustava <math>\begin{matrix}x = a_1\ \mbox{v}\ Z_{m1} \\ x = a_2\ \mbox{v}\ Z_{m2}\end{matrix}</math> má řešení.

# Platí d|(a₂–a₁) (tedy (a₂–a₁) je [[dělitelnost|dělitelné]] d).

 

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

 

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₃ = M₃^–1 = 9^–1 = 2 v Z₁₇ <br />

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

 

== Související články ==