# 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.

Tags :

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).