# Comparing orders induced by euclidean function and divisibility in euclidean domain

Let $(R,+,\cdot ,\Phi)$ be a euclidean domain where $\Phi$ denotes the Euclidean function, that is a function $R \setminus \lbrace 0 \rbrace \rightarrow \mathbb N$ such that :

$\forall a \in R \quad \forall b \in R \setminus \lbrace 0 \rbrace \quad \exists q,r \quad | \quad a=qb+r \quad \text{and} \quad (r=0 \quad \text{or} \quad \Phi(r) < \Phi(b))$

$\forall a \in R \quad \forall b \in R \setminus \lbrace 0 \rbrace \quad \Phi(a) \leq \Phi(ab)$

Define a strict partial order on $R$ by

$a < b \iff \Phi(a) < \Phi(b)$.

I strongly suspect that this order must have some relation with the order induced by divisibility. I wouldn't say that it's the same because I don't see why $\Phi(a) < \Phi(b)$ should imlply that $a|b$ but is there anything remarkable about these two partial orders ?

• What is ths Euclidean function? – William Elliot Jan 19 '18 at 9:09
• The one that gives meaning to the concept of euclidean domain. Let me edit to make it clearer. – user493048 Jan 19 '18 at 9:18

The answer is: not much. Consider the degree function $D$ over $\mathbb{Q}[X]$, which is an Euclidean function. Then $D(f)\leq D(g)$ does not imply anything about the divisibility of $f$ and $g$.
In fact, even in $\mathbb{Z}$ with the Euclidean function $|\cdot|$ you cannot infer any divisibility property from $|n|\leq|m|$. That's precisely why Euclidean domains are of some value, because the information we gain through the Euclidean function is not superfluous.
• Well we do have $P|Q \implies \text{deg}P \leq \text{deg}Q$ and $m|n \implies |m| \leq |n|$ – user493048 Jan 19 '18 at 9:58
• @user493048 Of course, but I understood your question as regarding an implication the other way around, which would be the interesting one! What you mention is just $\Phi(ab)\geq\Phi(a)$, the second axiom for Euclidean functions... – Jose Brox Jan 19 '18 at 20:20