WOLFRAM|DEMONSTRATIONS PROJECT

Extended GCD of Quadratic Integers

​
Q​
-2
​
Q​
-19
​
Q​
5
​
Q​
14
​
a
-100
b
-100
a'
-100
b'
-100
The associated ring of integers is [θ] with θ = 
2
.
This is a principal ring and for X, Y ∈ [θ],
X = -200θ,
Y = -200θ,
gcd(X,Y) = 100θ+100.
We verify that gcd(X, Y) divides both X and Y.
X = gcd(X, Y)(-1).
Y = gcd(X, Y)(-1).
The coefficients U, V of the extended gcd are
U = 0,
V = -1.
The Bézout identity in [θ] is UX + VY = gcd(X,Y), that is,
(-200θ)(0) +
(-200θ)(-1) = 100θ+100.
The fundamental unit here is ε = -1.
Then any element of the form
n
ε
(100θ+100) is also a gcd of X, Y.
Consider the quadratic field
Q(
d
)
and the associated ring of integers
[θ]
, where
θ=
d
if
d≡2,3(mod4)
and
θ=
1+
d
2
if
d≡1(mod4)
. We assume
[θ]
is principal but not necessarily Euclidean. We compute the GCD of two elements
X
,
Y
of
[θ]
modulo a unit of
Q(
d
)
. The computation also gives explicit coefficients
U
,
V
for the Bézout identity
Ux+Vy=gcd(X,Y)
. This is done by reducing binary quadratic forms and considering the sum of ideals
(a+bθ)(θ)+(a'+b'θ)(θ)
as the ideal
(m+nθ)(θ)
, with
m+nθ=gcd(a+bθ,a'+b'θ)
.