# Proof of infinitude of prime elements?

All proofs of infinitude of primes which I know of essentially prove that there are infinitely many irreducible elements of $\Bbb Z$, and with this goal in mind we can very easily extend this proof to many other rings (e.g. to $\Bbb Z[\sqrt{-d}],d\in\Bbb N$). Because in $\Bbb Z$ (and many other rings) it is known that all irreducible elements are prime elements. However, this isn't true always.

Suppose that we do not know that all irreducibles are prime. Is there any direct proof that there are infinitely many prime elements in $\Bbb Z$?

I am mainly interested in this because I hope for such proofs to generalize to rings in which implication "irreducible $\Rightarrow$ prime" is not true.

Edit: Here are my definitions. Let $R$ be a fixed commutative ring with unity and $p\in R$ any non-zero element.

Call $p$ irreducible if, whenever $p=a\cdot b,a,b\in R$ then exactly one of $a$ and $b$ is a unit.

Call $p$ prime if it's not a unit and whenever $p$ divides $a\cdot b$, then $p$ divides $a$ or $p$ divides $b$ (where we say that $x$ divides $y$ if $y=x\cdot z$ for some $z\in R$).

• The issue with the usual proof is that it relies on the fundamental theorem of arithmetic, of which there is no equivalent in rings that aren't unique factorization domains. – Matt Samuel Aug 2 '15 at 19:12
• Most authors usually also exclude $0$ from the definition of prime, since technically it otherwise satisfies it in an integral domain. (I don't know of any authors who include it, but it's less important in my opinion to exclude it than the units). – Matt Samuel Aug 2 '15 at 19:19
• Is there a particular class of rings that you are interested in? Another problem that can occur when trying to generalise the Euclidean proof is that in a general ring, if $p_1, \ldots, p_n$ are prime, then $p_1\ldots p_n + 1$ can be a unit. There are infinite UFDs with only finitely many primes. – Mathmo123 Aug 2 '15 at 19:21
• I suppose we must be. Perhaps I should rephrase: there are infinite UFDs with only finitely many primes up to associates, with an example being $\mathbb Z_{(p )} = \{\frac a{b} \in \mathbb Q: p\nmid b\}$ where $p$ is the only prime. – Mathmo123 Aug 2 '15 at 19:36
• More generally, there is a class of rings called "local rings" which are defined to be rings with exactly one maximal ideal. They're particularly important in number theory, where they allow us to look at things "locally" - i.e. one prime at a time. – Mathmo123 Aug 2 '15 at 19:37

Suppose that we do not know that all irreducibles are prime. Is there any direct proof that there are infinitely many prime elements in $\mathbb{Z}$?

Good question. Euclid's proof that there are infinitely many primes is in fact a proof that there are infinitely many irreducibles, and then elsewhere he uses the Euclidean algorithm to prove that if $p$ is irreducible and $p \mid ab$, then $p \mid a$ or $p \mid b$: i.e., that all irreducible elements are prime. Since existence of factorizations into irreducible elements in $\mathbb{Z}$ is quite clear by well-ordering, this latter result has all the content that $\mathbb{Z}$ is a unique factorization domain. Alternately, it follows easily from the Euclidean algorithm that every ideal in $\mathbb{Z}$ is principal, so $\mathbb{Z}$ is a PID hence also a UFD (although the proof of the "hence" is not as quick as a direct proof in the case of $\mathbb{Z}$). Assuming by a "direct proof" you mean an argument analogous to the proof of infinitely many irreducibles and not the Euclidean algorithm / PID / UFD stuff, my answer is not that I know of, no.

I do know of one partial streamlining: that $\mathbb{Z}$ is a UFD can be proved by an inductive argument, due to Lindemann and Zermelo: see e.g. the introduction to these notes. So one can use that and Euclid's proof of the infinitude of irreducibles and conclude that $\mathbb{Z}$ has infinitely many prime elements without having to go through the Euclidean algorithm or Euclid's Lemma (at least not explicitly: if you want to, you can see traces of these ideas in the inductive proof). But in terms of a "direct, one step argument": no, I don't think so!

I am mainly interested in this because I hope for such proofs to generalize to rings in which implication "irreducible ⇒ prime" is not true.

Great followup. I happened to be thinking of this kind of thing myself yesterday: in the context of a seminar on the process of mathematical research that I am (co-)leading, I presented an "axiomatic version" of Euclid's argument and then later asked myself what else this argument proves. It seems to me that irreducibles is a fundamental feature of this argument, and though there are variations -- including one which is justly popular on this site, that a ring with infinitely many elements and finitely many units has infinitely many maximal ideals -- I don't see how to squeeze prime elements out of this argument in any way.

Here is my abstract version of Euclid's argument:

Theorem: Let $R$ be a factorization domain (a.k.a. atomic domain: that is, every nonzero nonunit admits a factorization -- not necessarily unique! -- into a product of irreducibles) which is not a field and which satisfies Condition (E): for every nonzero element $x \in R$, there is $y \in R$ such that $yx+1$ is not a unit of $R$. Then $R$ has "infinitely many irreducibles", i.e., there is an infinite sequence $f_1,\ldots,f_n,\ldots$ of pairwise nonassociate irreducible elements.

You already know the proof: take any nonzero nonunit element of $R$ and factor it into irreducibles; that gives us one irreducible $f_1$. Inductively, having produced nonassociate irreducibles $f_1,\ldots,f_n$, by Condition (E) there is $y \in R$ such that $z = y f_1 \cdots f_n + 1$ is not a unit. It is also not zero, since that would force the $f_i$'s to be units. So $z$ has an irreducible factor $f_{n+1}$, which if it divided (and thus was associate to) $f_i$ for any $1 \leq i \leq n$, it would divide $z-y f_1 \cdots f_n = 1$ and thus be a unit.

For instance, one nice consequence of this is the following (again, at least a close cousin of other results which have been presented here and elsewhere):

Corollary: a) An infinite factorization domain which is not a field and which has finite unit group has infinitely many (nonassociate) irreducibles.
b) The set of all irreducible elements in a factorization domain is either empty (in the case of a field) or infinite (otherwise).

Some cases in which it is easy and pleasant to establish Condition (E) directly include a polynomial ring $R[t]$ over any domain $R$ and the Gaussian integers $\mathbb{Z}[i]$ (or the ring of integers of any imaginary quadratic field).

What is this Condition (E) really? It makes sense in any commutative ring and, for those who know about such things, is easily recognizable as saying that the Jacobson radical $J(R)$ -- i.e., the intersection of all maximal ideals -- is zero. Now observe that a Dedekind domain $R$ has $J(R) = (0)$ precisely when it has infinitely many prime ideals. So:

Theorem: A Dedekind domain has infinitely many prime ideals iff it has infinitely many (nonassociate) irreducibles.

Proof: As we just saw, Euclid's proof gives the forward direction. Conversely, a Dedekind domain with finitely many prime ideals is a PID, and then the distinction between prime ideals, prime elements and irreducible elements evaporates: up to associates, we have only finitely many irreducible elements.

Thus in some sense Euclid's argument is "the only way" to show that a Dedekind domain has infinitely many irreducible elements, although in any given case it may be easier or harder to pull off a direct verification of Condition (E).

For instance, for any number field $K$, the ring of integers $\mathbb{Z}_K$ is the integral closure of a Dedekind domain with infinitely many prime ideals ($\mathbb{Z}$) in a finite degree field extension, so over every prime ideal $(p)$ of $\mathbb{Z}$ there lies at least one prime ideal $\mathfrak{p}$ of $\mathbb{Z}_K$. So we have infinitely many prime ideals and thus infinitely many irreducible elements. But can you show Condition (E) directly in, say, $\mathbb{Z}[\sqrt{2}]$? It is not immediately obvious (to me) how to do so.

As in @Mathmo123's answer, it turns out to be the case that $\mathbb{Z}_K$ always has infinitely many prime elements. But I regard this as a quite deep result of algebraic number theory that lies far away from these "general algebraic" considerations. You need (don't you? do you??) to use Chebotarev Density to observe that the set of prime ideals of $K$ which split completely in the Hilbert class field of $K$ has positive density, and then use class field theory to deduce the result.

Let me try to persuade you that there is no "easy" connection between prime ideals and prime elements. Indeed, here is a striking construction of L.E. Claborn (see Example 1.5 here): let $R$ be any Dedekind domain which is not a PID, let $\mathcal{P}$ be the set of all prime elements of $R$ and put $\tilde{R} = R[\frac{1}{p} \mid p \in \mathcal{P}]$, i.e., the localization of $R$ with respect to the multiplicative set generated by all the prime elements. Then the pushforward map $\mathfrak{p} \rightarrow \mathfrak{p} \tilde{R}$ carries each principal prime ideal to the unit ideal and carries each nonprincipal prime ideal to a nonprincipal prime ideal. (In fact, it induces an isomorphism on the ideal class groups.) So $\tilde{R}$ is a Dedekind domain with infinitely many prime ideals but no prime elements!

Added: I just noticed that there is a result in the literature much stronger than some of the results I mentioned above.

Theorem (Cohen-Kaplansky, 1946): A factorization domain with only finitely many nonassociate irreducible elements has only finitely many prime ideals.

Proof: Consider a set of generators $X$ for a prime ideal $\mathfrak{p}$ in a factorization domain. For each element $x \in X$, some irreducible divisor $f_x$ of $X$ also lies in $\mathfrak{p}$, and thus $\{f_x \mid x \in X\}$ is also a set of generators, and the ideal so generated clearly does not change if we replace each $f_x$ by any associate element. We're done!

• That there should be many prime elements among integers of a number field could be seen from the finiteness of the ideal class group (by raising the generators of the group to the smallest powers to get principal ideals; the respective roots of the so obtained elements would generate a finite extension; look at prime ideals that split completely; references: Google, someone's notes that mention Kummer). – Albertas Jan 19 '16 at 13:57
• @Albertas: In (the proof of) Theorem 5.5 of alpha.math.uga.edu/~pete/Euclidean_Criterion.pdf, I explain how Cebotarev Density can be bypassed because the Cebotarev condition is a splitting condition. I still don't see how to avoid using the theory of the Hilbert Class Field. If you have a reference for that (a real one, I mean), please let me know. – Pete L. Clark Jan 19 '16 at 14:37
• I must apologize; it looked for a moment that an elementary counting argument says that an ideal cannot split completely and become principal simultaneously (I now see where I was incorrect). – Albertas Jan 19 '16 at 19:50

As per the comments, here is an analytic proof (due to Euler) that can be generalised to the ring of integers of a number field (a number field is a finite extension $K$ of $\mathbb Q$, and its integer ring is the ring of algebraic integers contained in it). This can then be used to show that $\mathbb Z[\sqrt d]$ has infinitely many primes. (If $d \not\equiv 1 \pmod 4$, then $\mathbb Z[\sqrt d]$ is the integer ring of $\mathbb Q(\sqrt d)$).

Consider the Riemann Zeta function $$\zeta(s) = \sum_{n=1}^\infty \frac{1}{n^s}$$ It is clear that $\lim_{s\to 1^+}\zeta(s) = \infty$. There is also a multiplicative form of the Riemann zeta function, convergent for $s>1$ given by $$\zeta(s) = \prod_{p \text{ prime}}(1-p^{-s})^{-1}$$ If there are only finitely many primes $p_1, \ldots, p_n\in\mathbb Z$, then using the second formula, $\zeta(s)$ is a finite product, and in particular, $\lim_{s\to 1^+}\zeta(s)$ is a finite product - this contradicts the fact that $\lim_{s\to 1^+}\zeta(s) = \infty$.

There is a generalisation of the Riemann zeta function, called the Dedekind zeta function, $\zeta_K(s)$, where $K$ is a number field, defined by $$\zeta_K(s) = \sum_{\mathfrak a\text{ an ideal}}(\mathbb N\mathfrak a)^{-s}$$where $\mathbb N\mathfrak a = \#(\mathcal O_K/\mathfrak a)$ is the ideal norm. When $K = \mathbb Q$, this is just the regular Riemann zeta function. Using the fact that in such rings, any ideal can be uniquely factorised into a product of prime ideals, we can show that $$\zeta_K(s) = \prod_{\mathfrak p\text{ a prime ideal}}(1-(\mathbb N\mathfrak p)^{-s})^{-1}$$ which gives the existence of infinitely many prime ideals similarly as before.

One can show that an infinite number of these ideals are principal, and using the fact that an element $x$ of a ring is prime if and only if the ideal it generates is prime, we can deduce that there are infinitely many prime elements.

• This is a really neat answer, but one would have to elaborate on stuff like why $\zeta_K$ should have a pole at $1$, why product formula should hold. I'm not going to ask you for that, because I suppose I can find this by just looking it up on web, and for now I'm not going to accept this, as someone might give a better answer. – Wojowu Aug 2 '15 at 20:24
• Perhaps I misunderstood, but it seems to me that the OP wants to prove that $\mathbb{Z}$ has infinitely many prime elements without having to know that every irreducible element in $\mathbb{Z}$ is prime. The latter is Euclid's Lemma and is equivalent to the uniqueness of factorization. The Euler product expansion of the zeta function is also equivalent to uniqueness of factorization. So it seems that this does not answer the question. – Pete L. Clark Aug 22 '15 at 1:08
• @PeteL.Clark I understood the question as asking for a proof of the infinitude of the primes in $\mathbb Z$ that can be generalised to other rings, in particular to rings of the form $\mathbb Z[\sqrt d]$. In the generalised version of the proof, we only need there to be unique factorisation of ideals, and not necessarily of elements. – Mathmo123 Aug 22 '15 at 20:33
• Well, the OP seems to be asking for a couple of things, and I agree that the statement that there are infinitely many prime elements in the ring of integers of any number field is an answer to his second question. But in terms of what you've shown: to factor the Dedekind zeta function you need to know that $\mathbb{Z}_K$ is a Dedekind domain. As soon as you know that, you know that it has at least one prime of $\mathbb{Z}_K$ lying over every integral prime, so there are infinitely many primes. – Pete L. Clark Aug 22 '15 at 22:51
• I don't see how the zeta function helps you unless you can establish some analytic property of it from scratch (which may be possible but seems a bit awkward to me). Then you have shown that there are infinitely many prime ideals of $\mathbb{Z}_K$. It is a much deeper fact that there are infinitely many prime elements: so far as I know, one needs things like Chebotarev density and class field theory to show this. So I'm having trouble finding the heart of your answer, if you see what I mean. I don't want to be too critical: everything you say is certainly correct and broadly relevant. – Pete L. Clark Aug 22 '15 at 22:53