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

• Google "Euclidean algorithm". The Wiki page (among others, I guess) can give you some answers. Note, also, that $a$ irreducible in a Euclidean domain, and $a$ doesn't divide $b$, imply $gcd(a,b)=1$, thus $ax+by=1$, which answers your first question. – Amitai Yuval Sep 28 '14 at 21:26
• it holds on way weaker hypotesis. If I don't get it wrong, it should be true also for UFD – Exodd Sep 28 '14 at 21:29
• Yes, among noetherian rings unique factorization is equivalent to the property that every irreducible is prime. – Kevin Arlin Sep 28 '14 at 21:33

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.

• Well, it seems to me that the hard (and important) parts are to show that every Euclidean domain is a PID, and that every PID is a UFD. – Amitai Yuval Sep 28 '14 at 21:33
• thanks for the answer! is there a direct way of proving that every irreducible element is a prime element? I mean only using the function which exists by def in an euclidean domain? – user179484 Sep 28 '14 at 21:45
• I can't think of one-was trying to do an induction on the Euclidean function of terms of a product an irreducible divides, but I don't see how to get the base case without using something we're trying to avoid. – Kevin Arlin Sep 29 '14 at 2:33

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

• Why did you suppose $u=px+ay?$ why does it holds? (in the first part of the proof) – user441848 Jul 18 '17 at 22:13
• @AnneliseToft my goal is to show that there is an unit $u$ such that $px+ay=u$. Then, using the definition of euclidean domain I prove that $r_n$ satisfies what I wanted to show. That's all. – Xam Jul 19 '17 at 1:34
• but you said you wanted to prove p is prime using (1), why are you making he assumption of u=px+ay? – user441848 Jul 19 '17 at 3:03
• @AnneliseToft "The idea is basically to show there exists an unit $u$ such that $u=px+ay$ for some $x,y\in D$ ... (1)" that's what I want to prove. Then, in the following line I explain how (1) works to show that $p$ is prime (which is ultimately what I want to prove). So, after I know that (1) will help me to my goal of proving that $p$ is prime, I prove that (1) is true. I mean, I find that $r_n$ is my $u$. – Xam Jul 19 '17 at 3:13
• oh ok thanks :) – user441848 Jul 19 '17 at 3:38