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.

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

- ServerfaultXchanger
- SuperuserXchanger
- UbuntuXchanger
- WebappsXchanger
- WebmastersXchanger
- ProgrammersXchanger
- DbaXchanger
- DrupalXchanger
- WordpressXchanger
- MagentoXchanger
- JoomlaXchanger
- AndroidXchanger
- AppleXchanger
- GameXchanger
- GamingXchanger
- BlenderXchanger
- UxXchanger
- CookingXchanger
- PhotoXchanger
- StatsXchanger
- MathXchanger
- DiyXchanger
- GisXchanger
- TexXchanger
- MetaXchanger
- ElectronicsXchanger
- StackoverflowXchanger
- BitcoinXchanger
- EthereumXcanger