Проширени Еуклидов алгоритам — разлика између измена
Садржај обрисан Садржај додат
м Робот: додато {{subst:User:Autobot/sandbox2}} |
м . using AWB |
||
Ред 23:
Да бисмо илустровали проширење [[Еуклидов алгоритам|Еуклидовог алгоритма]], размотримо израчунавање нзд(120, 23), који је приказан у табели лево. Приметимо да је количник у сваком дељењу забележен као и остатак.
У овом случају, делилац у последњем реду (који је једнак 1) нам говори да је нзд 1; то јест, 120 и 23 су узајамно прости (такође се називају и релативно прости). Због једноставности, изабрани примери су пар узајамно простих; али у општијем случају нзд-а који није 1, ово слично функционише.
Постоје два метода у наставку, од којих оба користе алгоритам целобројног дељења као подпоступак, од којих ће сваки бити засебно дискутован.
=== Итеративна метода ===
Линија 70 ⟶ 69:
У последњем реду стоји 1 = 120 × −9 + 23 × 47, што је тражено решење:
''x'' = −9 и ''y'' = 47.
Пошто је НЗД 1, ово такође значи да 47 даје мултипликативни инверз од 23 по модулу 120, а такође по модулу 23, -9 (или 14, који представљају исти елемент) даје мултипликативни инверз од 120 (или, еквивалентно, од 5).
Линија 308 ⟶ 307:
| ''x'' + 1
| ''x''<sup>4</sup> + ''x''<sup>2</sup>
| ''x''<sup>6</sup> + <
|-
| style="text-align:center;"| 5
| 1
| ''x'' + 1
| ''x''<sup>7</sup> + ''x''<sup>6</sup> + ''x''<sup>3</sup> + <
|-
| style="text-align:center;"| 6
Линија 326 ⟶ 325:
== Случај више од два броја ==
Можемо решити случај више од два броја итеративно. Прво, покажемо да <math>nzd(a,b,c) = nzd(nzd(a,b),c)</math>. Да бисмо доказали ово, нека је <math>d=nzd(a,b,c)</math>. По дефиницији nzd-а, <math>d</math> је делилац од <math>a</math> и <math>b</math>. Према томе <math>nzd(a,b)=k d</math> за неко <math>k</math>. Слично, <math>d</math> је делилац за <math>c</math> тако да је <math>c=jd</math> за неко <math>j</math>. Нека је <math>u=nzd(k,j)</math>. Према нашој конструкцији <math>u</math>-a, <math>ud | a,b,c</math> али пошто је <math>d</math> највећи делилац <math>u</math>-a је јединица. И пошто је <math>ud=nzd(nzd(a,b),c)</math> резултат је доказан.
Тако, ако <math>na + mb = nzd(a,b)</math>, онда постоје <math>x</math> и <math>y</math> такви да <math>xnzd(a,b) + yc = nzd(a,b,c)</math> па ће крајња једначина бити
: <math>x(na + mb) + yc = (xn)a + (xm)b + yc = nzd(a,b,c).\,</math>
Да би применили на n бројева користимо индукцију
:<math>nzd(a_1,a_2,\dots,a_n) =nzd(a_1,\, nzd(a_2,\, nzd(a_3,\dots, nzd(a_{n-1}\,,a_n)))\dots),</math>
Линија 343 ⟶ 342:
== Литература ==
{{refbegin}} -{
* {{Cite book|
}- {{refend}}
| |||