# Infinitely many primes in the ring of integers for any quadratic field

Let $d$ be an integer, not a perfect square, and $\mathcal{O}_K$ the ring of integers in $K = \mathbb Q(\sqrt d)$. I want to prove that there are infinitely many primes in $\mathcal{O}_K$.

How do we show that this is true? Thank you.

• Euclid's proof works without modification in this setting. – Qiaochu Yuan Apr 29 '11 at 18:29
• @Qiaochu: I'm not so sure, because if $\mathcal{O}_K$ is not a UFD, you don't necessarily have that every nonunit is a multiple of a prime element. For example, in $\mathbb{Z}[\sqrt{-5}]$, $3$ is not a prime and not unit, but there is no prime element that divides $3$ (since there is no element of norm $3$). So how do you guarantee that $p_1\cdots p_n + 1$ is divisible by some prime element? It works to show that there are infinitely many irreducible elements, but I don't see the prime element case. – Arturo Magidin Apr 29 '11 at 18:34
• @user9636: If you don't know about ideals or prime ideals, could you please edit the question and say what tools you do have available? What, if anything, have you proven about $\mathcal{O}_K$? – Arturo Magidin Apr 29 '11 at 18:43
• @Qia Even for irreducibles that doesn't generally work since the Eulerian constructed candidate may be a unit. – Bill Dubuque Apr 29 '11 at 21:09
• @Bill: point. This isn't an issue when $d$ is negative but when $d$ is positive you need to do some fiddling to ensure that the number you construct doesn't have norm $\pm 1$. – Qiaochu Yuan Apr 29 '11 at 21:17

I suspect you may have mistyped the question, or your professor may not have thought through his or her question carefully enough! Perhaps you are meant to be dealing with prime ideals, not elements?

That said, the result is true, and can be proved at a pretty elementary level, although I think that would be pretty hard for a homework problem. Here are some hints towards the most elementary proof I can think of, followed by some more thoughts.

(1) Let $R$ be a commutative ring and $p$ an element of $R$ such that $R/pR$ is an integral domain. Show that $p$ is prime. (I'm not sure what definition of a prime element you are working with, but this one should be equivalent to it.)

(2) Let $p$ be an odd prime such that $d$ is not square in $\mathbb{Z}/p \mathbb{Z}$. Show that $\mathcal{O}_K/(p \mathcal{O}_K)$ is isomorphic to the field with $p^2$ elements. In particular, $p$ is prime in $\mathcal{O}_K$.

We have now reduced to showing that there are infinitely many primes $p$ such that $d$ is not square modulo $p$.

(3) Show that there is an element $r$ in $\mathbb{Z}/(4d)\mathbb{Z}$, relatively prime to $4d$ such that, if $p \equiv r \mod 4d$ then $d$ is not a square modulo $p$.

Now, I don't know whether or not you are allowed to quote Dirichlet's theorem in your course. If you are, you are done. If not, I do know an elementary proof that there are infinitely many primes $p$ of $\mathbb{Z}$ such that $d$ is not a square modulo $p$, but I'd rather not write it out until I know you need it.

I worry that what I have written above may give you the wrong impression, that prime elements of $\mathcal{O}_K$ come from primes $p \in \mathbb{Z}$ for which $d$ is not square. That is only half the truth.

To make my life simple, let $p$ be relatively prime to $2d$.

If $d$ is not a square modulo $p$, then $\mathcal{O}_K/p \mathcal{O}_K$ is isomorphic to $\mathbb{F}_{p^2}$, as I discussed already. If $d$ is a square modulo $p$, then $\mathcal{O}_K/p \mathcal{O}_K \cong \mathbb{F}_p \oplus \mathbb{F}_p$. So $p$ is not prime.

The ideal $(p)$ factors as $\pi_1 \pi_2$, where $\pi_1$ and $\pi_2$ are prime ideals. It may or may not happen that $\pi_i$ is a principal ideal; if $\pi_i$ is principal, then its generator is a prime element of $\mathcal{O}_K$. What happens is that there is a finite group $H_K$, called the ideal class group, and $\pi$ represents an element of this group. The ideal $\pi$ is principal if and only if the corresponding element of $H_K$ is trivial.

It is in fact true that every element of $H_K$ is represented by $\pi$ for infinitely prime ideals $\pi$ of $\mathcal{O}_K$, and this is still true when we are dealing with "split primes", which in this case means prime ideals $\pi$ coming from a prime $p$ for which $d$ is square.

I worked out the particular case of $\mathbb{Q}(\sqrt{-23})$ in an earlier answer. But I don't know a general proof that every ideal class is represented by infinitely many prime ideals without going through class field theory.

• Or perhaps he is meant to be dealing with irreducible elements, for which Euclid's argument works. – Arturo Magidin Apr 29 '11 at 21:01

Remember that an element $\pi\in\mathcal{O}_K$ is a prime element if and only if for every $\alpha,\beta\in\mathcal{O}_K$, if $\pi$ divides $\alpha\beta$, then it divides either $\alpha$ or $\beta$.

Question. Are there any rational primes $p$ that are also primes in $\mathcal{O}_K$? If so, what are they? How many are there?

If the question has an affirmative answer and there are infinitely many such primes, then you'll be done. So let's consider what happens to a rational prime in $\mathcal{O}_K$.

We may assume that $d$ is not merely not a perfect square, but in fact squarefree, because if $d=r^2s$, then $\mathbb{Q}(\sqrt{d}) = \mathbb{Q}(\sqrt{s})$.

Consider the "norm map" $N\colon K\to\mathbb{Q}$ given by $$N(r+s\sqrt{d}) = (r+s\sqrt{d})(r-s\sqrt{d}) = r^2 - ds^2,\quad r,s\in\mathbb{Q}.$$ This map is multiplicative: if $\alpha,\beta\in\mathbb{K}$, then $N(\alpha\beta)=N(\alpha)N(\beta)$. Also, since $r+s\sqrt{d}$ satisfies the polynomial $$\Bigl( x - (r+s\sqrt{d})\Bigr)\Bigl(x - (r - s\sqrt{d})\Bigr) = x^2 - 2rx + (r^2-ds^2),$$ then $r+s\sqrt{d}\in\mathcal{O}_K$ if and only if $2r$ and $r^2 - ds^2\in\mathbb{Z}$.

This means that $r$ is either an integer or a half integer; if $r$ is an integer, then $ds^2$ must be an integer, hence $s$ must be an integer (since $d$ is squarefree). If $r$ is a half integer, $r = \frac{a}{2}$ with $a$ odd, then it is not hard to show that you must have $d\equiv 1 \pmod{4}$, and $s$ must also be a half integer.

It also means that we can translate statement about divisibility in $\mathcal{O}_K$ into statements about divisiblity in $\mathbb{Z}$, through the use of the map $N$. If $\alpha$ divides $\beta$ in $\mathcal{O}_K$, then $N(\alpha)$ has to divide $N(\beta)$ in $\mathbb{Z}$.

Now, suppose $p$ is a rational prime, and that $p$ divides a product $$\left( a + b\sqrt{d}\right)\left(x+y\sqrt{d}\right).$$ We want to know under what conditions we can conclude that $p$ divides either $a+b\sqrt{d}$ or $x+y\sqrt{d}$.

Since $p$ divides the product, that means that $N(p)= p^2$ divides the norm of the product, that is, $p^2$ divides $$N\left(\left(a+b\sqrt{d}\right)\left(x+y\sqrt{d}\right)\right) = N\left(a+b\sqrt{d}\right)N\left(x+y\sqrt{d}\right) = (a^2-db^2)(x^2-dy^2).$$ Since each of $a^2-db^2$ and $x^2-dy^2$ are integers, and $p^2$ divides the product, then $p$ must divide one of the factors. Without loss of generality, say that $p|a^2-db^2$.

Say $a$ and $b$ are both integers (think about the case where they are both half integers on your own later). Consider some possibilities:

1. If $p$ divides $b$, then it must divide $a$, and that means that $p$ divides $a+b\sqrt{d}$ and we are done.

2. If $p$ divides $a$, then it must also divide $db^2$, so it either divides $d$ or it divides $b$.

• If $p$ does not divide $d$, then it must divide $b$, and again we are done, since it divides both $a$ and $b$, hence it divides $a+b\sqrt{d}$.
3. If $p$ does not divide any of $a$, $b$, or $d$, then $a^2\equiv db^2\pmod{p}$, and since all of the factors are relative prime to $p$, that means that $d$ is a quadratic residue modulo $p$.

In summary: either $p$ divides $d$; or else $d$ is a quadratic residue modulo $p$; or else $p$ has to divide one of $a+b\sqrt{d}$ or $x+y\sqrt{d}$.

That is: if $p$ does not divide $d$, and $d$ is not a quadratic residue modulo $p$, then $p$ is a prime element of $\mathcal{O}_K$.

(This was under the assumption that $a$ and $b$ were integers; if they are both half integers, you'll get a similar conclusion).

So, the question now becomes:

Question (modified): Are there any rational primes $p$ for which $d$ is not a quadratic residue modulo $p$? How many?

Show there's infinitely many such primes for any given $d$. This (together with the completed argument given above) will show that there are infinitely many primes in $\mathcal{O}_K$, namely, at least as many as there are rational primes for which $d$ is not a quadratic residue.

Note that these are not all the prime elements in $\mathcal{O}_K$, though; for some primes $p$ that do not divide $d$ and for which $d$ is a quadratic residue, you get two prime elements of $\mathcal{O}_K$ that are not rational primes, for instance (infinitely many primes for sure, sometimes all such primes).

• Nice exposition. You hit most of the same points I did, but I think you did it more clearly. – David E Speyer Apr 29 '11 at 22:09
• @David: You are invoking some ring theory, I'm doing some congruences. I think both approaches have merit at this level (and I would have just used ideals if the OP had enough machinery at hand). – Arturo Magidin Apr 30 '11 at 2:36

Niven, Zuckerman, and Montgomery outline a topological proof that there exist infinitely many rational primes in Problem 52, Section 1.3, An Introduction to the Theory of Numbers, 5th ed., Wiley (New York), 1991. I have adapted the proof to the ring of quadratic integers.

Topologize $\mathcal O_K$ as follows: A set $\mathcal N$ of integers is open if for every $\nu \in \mathcal N$, there is an arithmetic progression $\mathcal A$ such that $\nu \in \mathcal A \subseteq \mathcal N$. Here, we define an arithmetic progression as a set $\{\rho + \kappa \delta\}$ of integers where $\delta \neq 0$ and $\rho$ are fixed integers, and $\kappa$ runs through all integers in $\mathcal O_K$.

Next, we prove that arbitrary unions of open sets are open and that finite intersections of open sets are open, which will show that these open sets define a topology in the usual sense: Let $\bigcup_i \mathcal N_i$ be an arbitrary union of open sets $\mathcal N_i$. For every $\nu \in \bigcup_i \mathcal N_i$, there is an arithmetic progression $\mathcal A$ such that $\nu \in \mathcal A$, namely the arithmetic progression in the particular $\mathcal N_i$ of which $\nu$ is an element. Hence, $\bigcup_i \mathcal N_i$ is open. Next, let $\mathcal N_i, i = 1, 2, \ldots, n$, be a finite number $n$ of open sets. If $\bigcap _{i=1}^n \mathcal N_i = \varnothing$, then $\bigcap _{i=1}^n \mathcal N_i$ is open trivially. Otherwise, let $\rho \in \bigcap _{i=1}^n \mathcal N_i$ so that $\rho$ is an element of each of the $n$ sets $\mathcal N_i$, and there is an arithmetic progression $\{\rho_i + \kappa \delta_i\}$ in each $\mathcal N_i$ of which $\rho$ is an element, so there is a particular $\kappa'$ such that $\rho = \rho_i + \kappa' \delta_i$. Then $\{\rho_i + \kappa \delta_i\} = \{\rho - \kappa' \delta_i + \kappa \delta_i\} = \{\rho + (\kappa - \kappa') \delta_i\} = \{\rho + \kappa \delta_i\}$. We can then make an arithmetic progression $\mathcal A = \{\rho + \kappa \delta_1 \delta_2 \delta_3 \dots \delta_n\}$ to claim that for every $\nu \in \bigcap _{i=1}^n \mathcal N_i$, there is the arithmetic progression $\mathcal A$ such that $\nu \in \mathcal A \subseteq \bigcap _{i=1}^n \mathcal N_i$. Hence, $\bigcap _{i=1}^n \mathcal N_i$ is open.

The next step is to prove that the complement of an arithmetic progression $\mathcal A = \{\rho + \kappa \delta\}$ is a union of arithmetic progressions: Let $\rho_1$ be any element in the complement of $\mathcal A$, in symbols, $\rho_1 \in \mathcal O_K \setminus \mathcal A$. If there is no such element, then the assertion is true vacuously. Otherwise, we first show that the arithmetic progression $\{\rho_1 + \kappa \delta\} \subset \mathcal O_K \setminus \mathcal A$. For suppose, to get a contradiction, that there is an integer of $\{\rho_1 + \kappa \delta\}$ in $\mathcal A$. Then there exist integers $\kappa_1, \kappa_2$ such that \begin{align} \rho_1 + \kappa_1 \delta & = \rho + \kappa_2 \delta\\ \rho_1 & = \rho + (\kappa_2 -\kappa_1) \delta\\ \rho_1 & \in \mathcal A \end{align} because $\kappa_2 -\kappa_1$ is one of the integers through which $\kappa$ runs to generate the elements of $\mathcal A$. But $\rho_1 \in \mathcal A$ contradicts $\rho_1 \in \mathcal O_K \setminus \mathcal A$. Hence, $\{\rho_1 + \kappa \delta\} \subset \mathcal O_K \setminus \mathcal A$. Next, make sets $\{\rho_i + \kappa \delta\}$ of arithmetic progressions for each of the elements $\rho_i$ in $\mathcal O_K \setminus \mathcal A$, and form their union $\bigcup_i \{\rho_i + \kappa \delta\}$. No element of the union will be in $\mathcal A$ as we just showed, and every element of $\mathcal O_K \setminus \mathcal A$ will be in the union, so $\mathcal O_K \setminus \mathcal A$ is a union of arithmetic progressions.

Because arithmetic progressions are open sets, and unions of open sets are open, it follows that the complement of an arithmetic progression is an open set.

Next, let $\mathcal U$ denote the union over all prime numbers $\pi$ of the arithmetic progressions $\{\kappa \pi\}$, and let $\mathcal V$ denote the complement of $\mathcal U$. In symbols, $\mathcal U = \bigcup_\pi \pi \mathcal O_K$, and $\mathcal V = \mathcal O_K \setminus \mathcal U$.

We now show that $\mathcal V$ is the set of units of $\mathcal O_K$ and therefore not open: Zero is not in $\mathcal V$ because $\kappa$ takes on the value $0$ as $\kappa$ runs through all the integers of $\mathcal O_K$. The other integers besides units are (not necessarily unique) products of primes, so those integers are not in $\mathcal V$. The units are in $\mathcal V$ because no unit has a prime factor. Based on our definition of an arithmetic progression, in particular that $\delta \neq 0$, $\mathcal V$ cannot contain an arithmetic progression and so is not open.

Finally, we show, to get a contradiction, that if there were only finitely many primes, $\mathcal V$ would be open. Now \begin{align} \mathcal V & = \mathcal O_K \setminus \mathcal U\\ & = \mathcal O_K \setminus \bigcup_\pi \pi \mathcal O_K\\ & = \bigcap_\pi \mathcal O_K \setminus \pi \mathcal O_K &&\text{(De Morgan's law)}\\ \end{align} The complement of of each $\pi \mathcal O_K$ is open as previously shown, and the intersection of a finite number of open sets is open as previously shown. Hence, $\mathcal V$ is open. But that contradicts that $\mathcal V$ is not open. Thus, there are infinitely many primes in $\mathcal O_K$.