Euclidean domain: every irreducible element is prime 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.
 A: 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$. 
A: A Euclidean domain is a unique factorization domain. So if $x$ is irreducible and divides $ab,$ then the unique factorization of $ab$ is the product of factorizations of $a$ and $b$, and by uniqueness $x$ must appear as one of those factors. 
A Euclidean domain is a principal ideal domain, so prime ideals are maximal. Since $a$ is irreducible, it's prime, that is, $(a)$ is a prime ideal and thus maximal. Since $a$ doesn't divide $b$, $b$ is nonzero in the quotient of our euclidean domain by $(a)$, which is a field, so that $b$ has an inversed modulo $(a)$. Translate this into a statement in the original ring.
The intuition for your third question is that this happens in the integers, and that euclidean domains are very similar to the integers. I'd offer the same intuition for the second question: in the integers an irreducible is just a prime number, so that this becomes the elementary fact of modular arithmetic that $\mathbb Z/p$ is a field.
