Wikipedie

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

Interaktivně procházet historii
← Přejít na předchozí porovnáníPřejít na další porovnání →
Smazaný obsah Přidaný obsah
VizuálníWikitext
BotMultichill (diskuse | příspěvky)
32 049 editací
m robot přidal: hu:Kínai maradéktétel
Dinybot (diskuse | příspěvky)
42 548 editací
m robot: typografické a kódové korekce a náhrady přesměrování podle specifikace
Řádek 20:
Nechť platí tvrzení "teoreticky číselná formulace". Zobrazení ''f'' z tvrzení "algebraická formulace" je [[homomorfismus]] zřejmě. Dále <math>f(x)=(a_1,\ldots,a_r)</math> právě tehdy, když ''x'' řeší soustavu příslušnou <math>a_1,\ldots,a_r</math>. Proto ''f'' je [[prostá funkce|prosté]] díky jednoznačnosti řešení a ''f'' je [[zobrazení na|na]] díky existenci řešení.
 
Nechť naopak platí "algebraická„algebraická formulace"formulace“, pak zobrazení <math>f^{-1}</math> poskytuje řešení soustavy z "teoreticky„teoreticky číselné formulace"formulace“. Jednoznačnost tohoto řešení plyne z prostoty ''f''.
 
==Zobecnění čínské věty==
Ať m<sub>1</sub>, m<sub>2</sub> jsou ''libovolná'' přirozená čísla, m<sub>i</sub> &ge;≥ 2 pro i = 1,2. Označme d = gcd(m<sub>1</sub>,m<sub>2</sub>), 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<br /><center><br />x = a<sub>1</sub> v Z<sub>m1</sub><br /> x = a<sub>2</sub> v Z<sub>m2</sub><br /> </center>má řešení.<br /><br />
# Platí d|(a<sub>2</sub>&ndash;a–a<sub>1</sub>).
 
Jestliže platí d|(a<sub>2</sub>&ndash;a–a<sub>1</sub>), je řešení určeno '''jednoznačně v Z<sub>M</sub>''', kde M = lcm(m<sub>1</sub>,m<sub>2</sub>), kde funkcí lcm(a,b) se rozumí [[nejmenší společný násobek]] čísel a, b.
 
==Příklad použití==
Máme spočíst zbytek čísla 12<sup>316 803</sup> po dělení číslem 26 741, neboli v Z<sub>26 741</sub>. Nejprve musíme mít daný [[prvočíselný rozklad]] čísla 26 741 = 11<sup>2</sup>&middot;·13&middot;·17. Protože čísla 11<sup>2</sup>, 13 a 17 jsou navzájem nesoudělná, je podle čínské věty o zbytcích číslo 12<sup>316 803</sup> v Z<sub>26 741</sub> určeno jednoznačně svými zbytky po dělení čísly 11<sup>2</sup>, 13 a 17.
 
Následně využijeme faktu, že a<sup>&phi;φ(m)</sup> = 1 v Z<sub>m</sub> ([[Eulerova funkce]]) a spočteme tyto zbytky:<br />
<br />
12<sup>316 803</sup> = 12<sup>110·2 880+3</sup> = 12<sup>3</sup> = 34 v Z<sup>121</sup><br />
12<sup>316 803</sup> = 12<sup>12·26 400+3</sup> = 12<sup>3</sup> = 12 v Z<sup>13</sup><br />
12<sup>316 803</sup> = 12<sup>16·19 800+3</sup> = 12<sup>3</sup> = 11 v Z<sup>17</sup><br /><br />
(protože &phi;φ(11<sup>2</sup>) = 110 ,&phi;φ(13) = 12 ,&phi;φ(17) = 16)<br />
 
Nyní použijeme čínskou vetu o zbytcích, kde m<sub>1</sub> = 11<sup>2</sup>, m<sub>2</sub> = 13 a m<sub>3</sub> = 17. Pak platí:<br />
Řádek 46:
M<sub>3</sub> = 11<sup>2</sup> · 13 = 1573<br />
<br />
N<sub>1</sub> = M<sub>1</sub><sup>&ndash;1–1</sup> = 100<sup>&ndash;1–1</sup> = 23 v Z<sub>121</sub><br />
N<sub>2</sub> = M<sub>2</sub><sup>&ndash;1–1</sup> = 3<sup>&ndash;1–1</sup> = 9 v Z<sub>13</sub> <br />
N<sub>3</sub> = M<sub>3</sub><sup>&ndash;1–1</sup> = 9<sup>&ndash;1–1</sup> = 2 v Z<sub>17</sub> <br />
Tudíž 12<sup>316 803</sup> = (34 · 221 · 23) + (12 · 2 057 · 9) + (11 · 1 573 · 2) = 1 728 v Z<sub>26 741</sub>
 
Řádek 59:
 
==Reference==
* RNDr. Jiří Velebil, Ph.D.: Diskrétní matematika a logika, [[České vysoké učení technické v Praze|ČVUT]] [[Praha]] [[2006]]
 
[[Kategorie:Algebra]]
Řádek 80:
[[ur:چینی تقسیم باقی مسلئہ اثباتی]]
[[vi:Định lý số dư Trung Quốc]]
[[zh:中国剩余定理]]▼
[[zh-classical:韓信點兵]]
▲[[zh:中国剩余定理]]
Citováno z „https://cs.wikipedia.org/wiki/Čínská_věta_o_zbytcích“