WisFaq!

Euclidisch algoritme

Hallo Wisfaq,

Ik wil graag ggd(135-14i,155+34i) berekenen via de Euclidische algoritme.Maar ik begrijp niet hoe dat moet.Het lukt me wel om de ggd te berekenen via expliciete priemfactorisatie in Z[i] (Z de integers).Ik heb zelf het volgende,

155+34i=1*(135-14i)+(20+48i)
135i-14i=6(20+48i)+15-302i)
20+48i=(15-302i)+(5+350i),
maar als ik zo door ga klopt er niets van.

Vriendelijke groeten,

Viky

viky
11-10-2004

Antwoord

Het algoritme werkt bijna net als in de natuurlijke getallen. Je deelt met rest: telkens doe je a=qb+r met 0rb.
In het complexe geval doe je ook een deling: a+bi=(p+qi)(c+di)+(r+si) waarbij de rest, dat is dus r+si, moet voldoen aan r²+s²c²+d² (of r=s=0). Dit geeft, net als in het gewone geval een dalend rijtje natuurlijke getallen en dat garandeert dat het proces een keer stopt.
Zie de link hieronder voor wat meer informatie

Zie PlanetMath over Euclidische valuaties [http://planetmath.org/encyclopedia/EuclideanValuation.html]

kphart
14-10-2004