Overleg:Uitgebreid algoritme van Euclides

weggehaald

Het volgende is de controle van het uitgebreide algoritme van Euclides. Het voorbeeld dat nu in het artikel staat is voldoende, dit is te technisch. ChristiaanPR (overleg) 12 okt 2015 10:54 (CEST)

Algoritme

De systematiek in de berekening laat zich als volgt beschrijven:

${\begin{matrix}r_{0}=a=x_{0}a+y_{0}b\\r_{1}=b=x_{1}a+y_{1}b\\r_{2}=a-q_{2}b=r_{0}-q_{2}r_{1}\\\cdots \\r_{n-1}=x_{n-1}a+y_{n-1}b\\r_{n}=x_{n}a+y_{n}b\\r_{n+1}=r_{n-1}-q_{n+1}r_{n}=(x_{n-1}-q_{n+1}x_{n})a+(y_{n-1}-q_{n+1}y_{n})b=x_{n+1}a+y_{n+1}b\\\cdots \\r_{N-1}=x_{N-1}a+y_{N-1}b\\r_{N}=x_{N}a+y_{N}b\\r_{N+1}=0\\\end{matrix}}$

Het best bezien we eerst de berekeningen na de eerste paar stappen. Van de nieuwe $'a'=r_{n-1}$ en $'b'=r_{n}$ wordt de nieuwe rest $r_{n+1}=r_{n-1}-q_{n+1}r_{n}$ bepaald. In de vorige stappen zijn de resten $r_{n-1}$ en $r_{n}$ uitgedrukt als gehele lineaire combinatie van de oorspronkelijke getallen a en b, met coëfficiënten respectievelijk $x_{n-1}$ en $y_{n-1}$ en $x_{n}$ en $y_{n}$. Daarmee laat ook de nieuwe rest $r_{n+1}$ zich in a en b uitdrukken, met coëfficiënten $x_{n+1}=x_{n-1}-q_{n+1}x_{n}$ en $y_{n+1}=y_{n-1}-q_{n+1}y_{n}$. Het algoritme loopt af als de rest 0 wordt. De vorige rest is de gezochte g.g.d. uitgedrukt als gehele lineaire combinatie van a en b. Om het algoritme te beginnen, kiezen we als startwaarden $r_{0}=a$ en $r_{1}=b$.

Rekenschema

In het rekenschema van het algoritme houden we de rij met resten r bij en daarnaast de resultaten q van de deling, alsmede de coëfficiënten x en y, die dezelfde structuur vertonen als de resten. Als startwaarden kiezen we:

$r_{0}=\max(a,b)\,$

$r_{1}=\min(a,b)\,$

$x_{0}=1\;$

$x_{1}=0\;$

$y_{0}=0\;$

$y_{1}=1\;$

We bepalen de nieuwe rest r en het resultaat q van de deling door:

$q_{n+1}=r_{n-1}\div r_{n}\;$

$r_{n+1}=r_{n-1}-q_{n+1}r_{n}\;$

en vervolgens de nieuwe coëfficiënten uit:

$x_{n+1}=x_{n-1}-q_{n+1}x_{n}\;$

$y_{n+1}=y_{n-1}-q_{n+1}y_{n}\;$

Het algoritme loopt af als de nieuwe rest gelijk is aan 0.

Voorbeeld, vervolg

Voor het voorbeeld ziet dat er zo uit:

${\begin{matrix}r&q&x&y\\1140&&1&0&&&1140&=&1\times 1140+0\times 900\\900&&0&1&&&900&=&0\times 1140+1\times 900\\240&1&1&-1&&&240&=&1\times 1140-1\times 900\\180&3&-3&4&&&180&=&-3\times 1140+4\times 900\\60&1&4&-5&&&60&=&4\times 1140-5\times 900\\\end{matrix}}$

ChristiaanPR (overleg) 12 okt 2015 10:54 (CEST)