Проширени Еуклидов алгоритам — разлика између измена
Садржај обрисан Садржај додат
Нова страница: {{МАТФ052013}} '''Проширени Еуклидов алгоритам''', поред проналажења највећег заједничког делиоц… |
Нема описа измене |
||
Ред 166:
Претпоставимо <math>d_i = d_{i-2} - k_{i-1} \cdot d_{i-1}</math>. Онда мора бити
:<math>x_i = x_{i-2} - k_{i-1} \cdot x_{i-1}</math>
:<math>y_i = y_{i-2} - k_{i-1} \cdot y_{i-1}.</math>
Ред 173:
Заправо, обављање табличног метода је једноставније него што се то да закључити из горенаведених једнакости. За налажење трећег реда у табели у примеру, само приметимо да се 120 подељено са 23 појављује 5 пута са остатком. То нам даје ''k'', мултипликативни фактор за овај ред. Сада, свака од вредности у табели је вредност два реда изнад ње, минус ''k'' пута вредност одмах испод ње. Ово коректно води до
:<math>x_3 = 1 - 5 \cdot 0 = 1</math>,
:<math>y_3 = 0 - 5 \cdot 1 = -5</math>,
:<math>d_3 = 120 - 5 \cdot 23 = 5.</math>
Након понављања овог метода у циљу налажења сваког реда табеле (приметимо да су остатак записан у табели и мултипликативни фактор два различита броја!), коначне вредности за <math>x</math> и <math>y</math> ће решити <math>ax + by = nzd(a, b)\,</math>:
| |||