WOLFRAM|DEMONSTRATIONS PROJECT

Euclidean Algorithm in the Ring of Algebraic Integers Generated by the Square Root of Five

​
β = a + bϕ
a
100
b
47
α = c + dϕ
c
10
d
3
β = 100+47ϕ
α = 10+3ϕ
100+47ϕ = (10+ϕ) × (10+3ϕ) + (-3+4ϕ)
10+3ϕ = (3ϕ) × (-3+4ϕ) + (-2)
-3+4ϕ = (1-2ϕ) × (-2) + (-1)
-2 = (2) × (-1) + (0)
This Demonstration shows examples of arithmetic operations in the field
(
5
)
, the field of numbers
a+b
5
, where
a
and
b
are rational numbers. But instead of using the numbers 1 and
5
, here we use 1 and the golden ratio
ϕ=
1
2
(1+
5
)
.
First define the conjugate of
z=x+y
5
∈(
5
)
to be
z
=x-y
5
. Also define the norm of
z=x+y
5
to be
z
z
=Nx+y
5
=x+y
5
x-y
5
=
2
x
-5
2
y
.
An algebraic integer in the field
(
5
)
is of the form
1
2
(a+b
5
)
, where
a≡b(mod2)
. If a number is an algebraic integer, its norm is an ordinary integer.
Write
1
2
x+y
5

as
1
2
(x-y)+
1
2
y(1+
5
)=a+bϕ
, with
x
,
y
,
a
and
b
integers.
So
N(a+bϕ)=
2
a+
b
2
-
5
4
2
b
.
Suppose that
α
and
β
are algebraic integers in
(
5
)
. In the field
(
5
)
, the quotient
μ=β/α
can be written as
a+bϕ
, where
a
and
b
are rational. Let
λ=c+dϕ
be such that
a-c⩽
1
2
and
b-d⩽
1
2
. Then
N(μ-λ)<1
. If
γ=β-λα
then
β=λα+γ
, where
N(γ)<N(α)
.
In the case of division in algebraic integers, we show the pair
{λ,γ}
. This Demonstration shows the Euclidean algorithm in the ring of algebraic integers of
(
5
)
:
β=
λ
0
α+
α
1
,
N(
α
1
)<N(α)
,
α=
λ
1
α
1
+
α
2
,
N(
α
2
)<N(
α
1
)
,
α
2
=
λ
2
α
2
+
α
3
,
N(
α
3
)<N(
α
2
)
,
...
α
n-1
=
λ
n
α
n
+
α
n+1
,
N(
α
n+1
)<N(
α
n
)
,
α
n
=
λ
n+1
α
n+1
.