Division on a real quadratic ring of integers.

by del42z   Last Updated October 20, 2018 05:20 AM

I've seen that $\mathbb{Z}[\varphi ] = \mathcal{O}_{\mathbb{Q}_{\sqrt{5}}}$, where $\varphi$ is the golden ratio, is a Euclidean domain with norm $N(x + y\varphi ) = x^{2} + xy - y^{2}$.

Given a particular $a, b\in\mathbb{Z}[\varphi ], b \neq 0$, I want an algorithm(that can be written in code) to find $q, r \in \mathbb{Z}[\varphi ]$ such that $a = qb + r, \; |N(b)|>|N(r)$| or $r = 0$.

Here's what I've come up with so far. If $b = c + d\varphi$, then let $b' = (c+d)-d\varphi$. It can be shown that $bb' = N(b)$.

If we set $q_{0} = ab'/N(b)$ then we have $a = bq_{0}$, but we have no guarantee that $q_{0}$ is in $\mathbb{Z}[\varphi ]$. We need some way of 'rounding' $q_{0}$ to get $q\in\mathbb{Z}[\varphi ]$ so a suitable $r$ falls out. It's this 'rounding' that I don't know how to execute.

Answers 1

We let $\phi={1+\sqrt5\over2}$. Given $a,b$ in ${\bf Z}[\phi]$, $b\ne0$, we let $a/b=q_0=s+t\phi$ with $s,t$ rational. We choose integers $u,v$ with $|s-u|\le1/2$ and $|t-v|\le1/2$. We let $q=u+v\phi$, so $q\in{\bf Z}[\phi]$, and let $r=a-bq$, so also $r\in{\bf Z}[\phi]$. Also, $r=a-bq_0+b(q_0-q)=b\bigl((s-u)+(t-v)\phi\bigr)$. Then writing $N$ for the norm we have $|N(r)|=|N(b)||\bigl((s-u)^2+(s-u)(t-v)-(t-v)^2\bigr)|\le(1/2)|N(b)|$ (using the trivial estimate $|x^2+xy-y^2|\le1/2$ for $|x|\le1/2$, $|y|\le1/2$ – we could do better, but this is more than good enough to answer the question).

Gerry Myerson
Gerry Myerson
October 20, 2018 05:13 AM

Related Questions

Finite number of steps to solve a problem

Updated December 25, 2017 10:20 AM