How to prove:
In a Euclidean domain every irreducible element is prime.
My script also says : if $a$ is irreducible (also in an euclidean domain) and if $a$ does not divide $b$ then there is a $c$ such that $a$ divides $(bc-1)$. How can I prove it and what is the intuition behind it?
It also says (still working with an euclidean domain): if $\gcd(a,b)=g$ then there exist $x,y$ such that $g=ax+by$. Is there a simple proof of this ? Whats the intuition behind it? By simple proof I mean a proof which gives insight into why it is like this. I understand the proofs, where you prove that for any $a,b$ the set $\{as+br\mid s,r\}$ out of the euclidean domain is an ideal, but it doesnt help my intuition.
Best Answer
It can be proved directly that in an Euclidean domain $D$ every irreducible element is prime. Let's call $p$ our irreducible element, if $p\mid ab$ and $p\not\mid a$, we have to prove that $p\mid b$. The idea is basically to show there exists an unit $u$ such that $u=px+ay$ for some $x,y\in D$ ... $(1)$
First, let's see how to prove that $p$ is prime using $(1)$. This is very classical because if $$\;\;\;\;px+ay=u$$ $$\implies pxb+ayb=ub.$$
So by hypothesis $p\mid ayb$ and also $p\mid pxb$, therefore $p\mid ub$. Since $ub\mid b$, it follows that $p\mid b$. Hence $p$ is prime.
Now, how can we show that $u=px+ay$ ? Here is where we use the hypothesis that $D$ is Euclidean. Let's write $\delta$ for the euclidean valuation in $D$, for $a$ and $p$ there are $q_1$ and $r_1$ such that $a=pq_1+r_1$, $\delta(r_1)<\delta(p)$ and $r_1\neq 0$, otherwise $p\mid a$, which is against our assumption. If we divide $p$ by $r_1$ we can find $q_2$ and $r_2$ such that $p=r_1q_2+r_2$ and $\delta(r_2)<\delta(r_1)$. We can perform the same process several times but at some point we have to stop because otherwise we eventually would get a decreasing sequence of positive integers $\ldots<\delta(r_n)<\delta(r_{n-1})<\ldots <\delta(r_1)<\delta(p)$, which is absurd.
Let's suppose that we stop at $r_n$, then we have something like this: \begin{array}{cc} a=pq_1+r_1; \;\delta(r_1)<\delta(p)\\ p=r_1q_2+r_2; \;\delta(r_2)<\delta(r_1)\\ \vdots\\ r_{n-2}=r_{n-1}q_n+r_n; \;\delta(r_n)<\delta(r_{n-1})\\ r_{n-1}=r_nq_{n+1}. \end{array}
We claim that $r_n$ divides both $a$ and $p$, $r_n$ is an unit and we can write it as $r_n=px+ay$ for some $x,y\in D$.
Indeed, since $r_n\mid r_{n-1}$ it follows that $r_n\mid r_{n-2}$ and successively we deduce by the above equations that $r_n\mid r_i$, for every $1\le i\le n$, so $r_n\mid p$ and thus $r_n\mid a$. Now, since $p$ is irreducible, $r_n$ must be an unit or an associate of $p$. If $r_n$ and $p$ are associates we would have $p\mid r_n$, then $p\mid a$, contradiction. Therefore $r_n$ is an unit of $D$.
Finally, using the same idea given in the proof of the theorem 3.5 of this paper we can by reversing steps write $r_n$ as $px+ay$ for some $x,y\in D$.
Remark: The above proof doesn't use the fact that $r_n$ is actually a $\gcd$ of $a$ and $p$. We only need the fact that $r_n$ is a common divisor of $a$ and $p$.