# Extended GCD of Quadratic Integers

Extended GCD of Quadratic Integers

Consider the quadratic field and the associated ring of integers , where if and if . We assume is principal but not necessarily Euclidean. We compute the GCD of two elements , of modulo a unit of . The computation also gives explicit coefficients , for the Bézout identity . This is done by reducing binary quadratic forms and considering the sum of ideals as the ideal , with .

Q(

d

)[θ]

θ=

d

d≡2,3(mod4)

θ=

1+

d

2

d≡1(mod4)

[θ]

X

Y

[θ]

Q(

d

)U

V

Ux+Vy=gcd(X,Y)

(a+bθ)(θ)+(a'+b'θ)(θ)

(m+nθ)(θ)

m+nθ=gcd(a+bθ,a'+b'θ)