Introduction to UFDs

(This is Glen.)

I was sorting through the LaTeX files on my computer and unearthed an old set of solutions to a mysterious problem set, dated 2020. After a bit of digging in some old Discord servers, I found out that these were solutions to one of Zhao Yu's sets for some RI training, which I had presumably crashed because it was online (thanks to Covid) and I was too free or something. Anyway, this file contained a lengthy introduction to UFDs, which I had recently learnt about in uni and had used to overkill a couple of problems in the set. This is, I think, quite suitable for a blog post, so here we are.

The fundamental theorem of arithmetic

As a warmup, let's think about something we learn about in primary school (well, at least I remember learning about this in primary school but I am old so this may no longer be the case): the unique prime factorisation of integers.

(Fundamental theorem of arithmetic) Each integer $n>1$ can be written uniquely as $n=p_1\cdots p_k$, where the $p_i$ are primes, up to reordering of the prime factors.

To be specific, this says two things:

1. Each $n>1$ can be written as $n=p_1\cdots p_k$, where the $p_i$ are primes.
2. If $p_1\cdots p_k = q_1\cdots q_\ell$ are products of primes, then $k=\ell$ and the $p_i$ are a reordering of the $q_j$.

To clarify, by "prime number" I mean a positive integer that's only divisible by itself and $1$.

Let's try to prove this - it's trickier than you might think! The first point isn't that bad: suppose $n$ is not prime, then it has a factor that isn't $1$ or $n$. Pick the smallest such factor, then this has to be a prime $p$. Divide $n$ by $p$, and repeat inductively. The process eventually stops because the value of $n$ decreases each time we divide.

The second point is the hard one. What we want to show is probably something along the lines of: $p_1$ divides the RHS, so one of the $q_j$ is equal to $p_1$, then we can cancel both terms and induct, which means we want some result of the form "if a prime $p$ divides the product $a_1\cdots a_k$, then $p$ divides one of the $a_i$". But why is this true? Well, sure, you might think it's intuitively true, but that's probably because the uniqueness of prime factorisation is so deeply ingrained that it's just common sense. However, we can't quote this, since then our proof would be circular. So what now?

It turns out that the answer is some other fundamental thing which we first learn about in Senior Team (again, I'm old so the syllabus may have changed, etc. etc.): the Euclidean algorithm.

The Euclidean algorithm

Let's recall what this is. Suppose we have two positive integers $a,b$, and we want to find $\gcd(a,b)$ (defined to be the largest positive integer which divides both of them). One way to do this (as I learnt in primary school) is to prime factorise both numbers, and then pick the minimum exponent of each prime. But we're trying to prove the uniqueness of prime factorisation, so we can't do this. Instead, there is an algorithm which everyone who does olympiads has heard about thanks to IMO 1959/1: the Euclidean algorithm. Here's how it goes: at each step, replace the larger of the numbers (WLOG $b$) with its remainder when divded by $a$; terminate when said remainder is $0$.

Here's an example: let's say $a=267,b=31$. Then we go $(267,31) \rightarrow (19,31) \rightarrow (19,12) \rightarrow (7,12) \rightarrow (7,5) \rightarrow (2,5) \rightarrow (2,1) \rightarrow (0,1)$, so the algorithm outputs $1$.

Why does this work? Well, $k|a$ and $k|b$ iff $k|a$ and $k|(b-a)$, so $\gcd(a,b) = \gcd(a,b-a)$. Combine this with the fact that $\gcd(m,0)=m$ and induct.

Great, but why is this useful? It turns out that this gives a (constructive!) proof of:

(Bézout's theorem) Let $a,b$ be integers. Then there exist integers $m,n$ such that $am+bn = \gcd(a,b)$.

The idea of the proof is to "reverse" the Euclidean algorithm. I don't want to write down a bunch of algebra, so I'll illustrate it with the example from above. Rewrite the steps of our algorithm as: $$\begin{align*}267 - 8\times 31 &= 19 \\ 31 - 19 &= 12 \\ 19 - 12 &= 7 \\ 12 - 7 &=5 \\ 7-5 &= 2 \\ 5 - 2\times 2 &= 1\end{align*}$$ Now, substitute everything in turn: $$\begin{align*} 19 &= 267 - 8\times 31 \\ 12 &= 31 - (267 - 8\times 31) = 9\times 31 - 267 \\ 7 &= (267-8\times 31) - (9\times 31 - 267) = 2\times 267 - 17\times 31 \\ 5 &= (9\times 31 - 267) - (2\times 267 - 17\times 31) = 26\times 31 - 3\times 267  \\ 2 &= (2\times 267 - 17\times31) - (26\times 31 - 3\times 267) = 5\times 267 - 43\times 31 \\ 1 &= 26\times 31 - 3\times 267 - 2(5\times 267-43\times31) = 112\times 31 - 13\times 267\end{align*}$$

With this in hand, we can prove the uniqueness half of the fundamental theorem of arithmetic.

Uniqueness of prime factorisation

We'll show that if $p|ab$ for $p$ prime, then $p|a$ or $p|b$. Indeed, suppose $p$ doesn't divide $a$, then $\gcd(a,p)=1$ (since it can't be $p$), and so by Bézout, there exist integers $m,n$ for which $pm + an = 1$. Multiply $b$ to both sides, then we have $pmb + abn = b$. But the LHS is divisible by $p$, so $p|b$.

Now, induction on $k$ tells us that if $p|a_1\cdots a_k$, then $p|a_i$ for some $i$, which is exactly the fact that we needed to complete the proof.

I'm not too sure how new this is to you (I, for one, went through most of my life without ever thinking about why the fundamental theorem of arithmetic is true), but in any case, you should be warmed up for what comes next.

Unique factorisation domains

We want to generalise the idea of unique factorisation of integers. These end up being mathematical objects called rings. Roughly speaking, a ring is a set of numbers with the operations $+,-,\times$ in the usual sense, but not $\div$. Specifically it's a set $R$ with operations $+$ and $\times$ such that:

• $+,\times$ are associative
• $+$ is distributive over $\times$
• $+$ is commutative
• there exist elements $0,1\in R$ such that $0+a = 1\times a = a\times 1 = a$ for all $a\in R$
• for every $a\in R$, there exists an element $-a\in R$ such that $a + (-a) = 0$.

Additionally, we also tend to assume that $\times$ is commutative.

Here are some examples of rings: $\mathbb{Z}$,$\mathbb{Q}$, $\mathbb{R}$, $\mathbb{Z}[X]$ (polynomials in $\mathbb{Z}$), $\mathbb{R}[X,Y,Z]$, $\mathbb{Z}/n\mathbb{Z}$ (integers mod $n$),  $\mathbb{Q}[i] = \{a+bi|a,b \in \mathbb{Q}\}$, continuous functions $f:\mathbb{R}\rightarrow\mathbb{R}$ (with pointwise addition and multiplication). $n\times n$ matrices also work if we allow $\times$ to not be commutative. $\mathbb{N}$ is not a ring because it fails the last property.

A ring is an integral domain if $ab = 0 \Rightarrow a=0$ or $b=0$. A non-example would be $\mathbb{Z}/4\mathbb{Z}$, since $2\times2 = 0$ in this ring. All our rings with be integral domains from now on.

Now, for an integral domain $R$, we want to generalise our definition of unique prime factorisation. To do this, we have to fix our definition of "prime". I guess we're all used to the definition that says that a prime number is an integer that's only divisible by $1$ and itself, but that's not entirely accurate: if one is being extremely pedantic, a prime number $p$ has four factors $1,-1,p,-p$. Of course, this is kind of silly because $p$ and $-p$ are "the same"; they differ by multiplication by $-1$, which doesn't really matter, because it has a multiplicative inverse (itself). So the multiples of $p$ are exactly the multiples of $-p$, and hence they are really the same thing for divisibility purposes.

Elements which have a multiplicative inverse (i.e. $a$ for which $ab=1$ for some $b$) are called units. For example, in $\mathbb{Z}$, the units are $\pm1$ while in $\mathbb{R}$, the units are everything except for $0$. Our definition of prime generalises as follows: $p\in R$ is called irreducible if $p\ne 0$, $p$ is not a unit, and $a|p$ (i.e. $p=ab$ for some $b$) implies $a$ is a unit or $p$ times a unit.

Confusingly, ring theorists also have a definition for "prime": $p\in R$ is called prime if $p\ne 0$, $p$ is not a unit, and $p|ab \Rightarrow p|a$ or $p|b$.

(A note on the conditions $p\ne0$ and $p$ is not a unit: this should intuitively make sense since we don't call $0$ and $1$ prime numbers.)

In $\mathbb{Z}$, "prime" and "irreducible" are just our usual notions of prime, but in general, these do not have to coincide! We'll see some examples later. Even so, they are still related: primes are irreducible. Indeed, if $p$ is prime and $p=ab$, then $p|a$ or $p|b$. In the former case, $a = pq$ for some $q$, so $p = pqb$, i.e. $p(1-qb) = 0$. Since $p\ne 0$, then $qb=1$, so $b$ and $q$ are units, and $a=pq$ is $p$ times a unit. In the latter case, a similar argument shows that $a$ is a unit.

We are finally ready to define a UFD. A unique factorisation domain is an integral domain $R$ such that for each nonzero $n\in R$,

1. $n$ can be written as $n = up_1\cdots p_k$, where $u$ is a unit and the $p_i$ are irreducibles.
2. If $p_1\cdots p_k = q_1\cdots q_\ell$ are products of irreducibles, then $k=\ell$ and we may reorder the $q_j$ such that for each $i$, $p_i$ and $q_i$ differ by multiplication by a unit.

(In the case where $n$ is a unit, we have $k=0$.)

The annoying wording of the second point is to allow things like $2\times3\times5 = (-2)\times3\times(-5)$. When working over integers, we can always choose our irreducibles to be positive, but in general, rings don't have any notion of positive or negative, so we have to bake the ambiguity of multiplying by units into the definition.

The fundamental theorem of arithmetic says that $\mathbb{Z}$ is a UFD. Additionally, somewhat tautologically, all fields (e.g. $\mathbb{Q},\mathbb{R},\mathbb{C}$) are UFDs. But what else?

Before we proceed, first let us note that we may replace the second condition with: "all irreducibles are primes". Indeed, this implies the original second condition using our inductive argument from the $\mathbb{Z}$ case, and conversely, in a UFD, if $p|ab$ for an irreducible $p$, then we can prime factorise both $a$ and $b$, and $p$ (times a unit) must appear in one of their prime factorisations. This is, in general, the more useful version of the definition of a UFD.

Euclidean domains

When we proved that $\mathbb{Z}$ is a UFD, we used the Euclidean algorithm. What exactly made it work? We needed to be able to take the remainder of the "bigger" number when divided by the "smaller" number, and this remainder had to be "smaller" than both the original numbers, so the algorithm could eventually terminate. But in general, we don't really have a notion of bigger or smaller (how do you compare two continuous functions from $\mathbb{R}$ to $\mathbb{R}$?) 

In fact, this is also problematic because now our usual definition of a gcd doesn't work. This can be fixed in the following way: $d$ is a gcd of $a,b$ if $d|a,d|b$ and for all $d'$ such that $d'|a, d'|b$, we have $d'|d$. So instead of being "greatest" by size, $d$ is now "greatest" in the sense that it contains all other common divisors. Note that gcds are now only well-defined up to multiplication by a unit (in $\mathbb{Z}$, $d$ and $-d$ can both be gcds but we just pick the positive one by convention): if $d|d'$ and $d'|d$, i.e. $d=d'a$ and $d'=db$, then $d(ab-1)=0$, so $a,b$ are units.

Anyway, a gcd is a thing that can be defined in general rings. Now, if we can define a notion of bigger/smaller that makes the Euclidean algorithm work, then we have a Euclidean domain.

More specifically, a Euclidean domain is an integral domain $R$ with a "size" function $f: R \rightarrow \mathbb{Z}_0^{+}$ such that

• $f(r) = 0$ iff $r=0$
• for each nonzero $a,b\in R$, we may write $a=bq+r$ where $f(r) < f(b)$ (so we have a notion of "remainder")

For $R=\mathbb{Z}$, $f(r) = |r|$ works. A more non-trivial example is $\mathbb{R}[X]$, for which the degree is a valid $f$ (because of polynomial long division).

Euclidean domains are UFDs

Now would be the time to scroll up to the section on the Euclidean algorithm and check that in a Euclidean domain, the Euclidean algorithm terminates, and that its output is a gcd. Moreover, the same arguments give us Bézout's theorem, from which we may deduce (as in the $\mathbb{Z}$ case) that irreducibles are prime.

On the other hand, all nonzero $n\in R$ have a factorisation into irreducibles: If $n$ is irreducible, we're done. Otherwise, we may write $n=ab$, where neither $a$ nor $b$ is a unit or $n$ times a unit. We want $f(a),f(b)<f(n)$, so we may induct. Suppose that $f(a)\ge f(n)$. Then, applying the Euclidean algorithm on $a,n$, the first step is $a - nq = r$. If $r=0$, then $a|n$ and $n|a$, so $a$ is $n$ times a unit, contradiction. Hence, the Euclidean algorithm terminates after the first step, and so gives us some gcd $a'$ of $a,n$ for which $f(a') < f(n)$. But now $a,a'$ are both gcds for $a,n$, so $a$ is $a'$ times a unit. We may thus rewrite $n=ua'b'$, where $u$ is a unit and $f(a'),f(b') < f(n)$, and then we're done by induction.

The second paragraph here is somewhat annoying and technical, but really, the main property that we'll be using is the result of the first paragraph.

Actual olympiad usage

You might be wondering why I've put you through that long ramble on abstract algebra. If so, here comes the pay-off.

Primes that are 1 mod 4

The following lemma is a semi-famous fact which has various proofs, none of which I could ever reproduce except for the UFD proof.

Let $p\equiv 1\pmod 4$ be a prime number. Then $p=a^2+b^2$ for some integers $a,b$.

As far as I know, all proofs use the fact that $-1$ is a quadratic residue mod $p$, i.e. there's an integer $n$ such that $p|n^2+1$. You can prove this using the existence of a primitive root, but actually, there's an even more low-powered way of showing this using Wilson's theorem: $$\left(\frac{p-1}2\right)!^2 \equiv \left(1\times 2 \times\cdots \times \frac{p-1}2\right) \times \left((-1)\times (-2) \times\cdots \times \left(-\frac{p-1}2\right)\right) \equiv (p-1)! \equiv -1\pmod{p}$$

So we have $p|n^2+1$. Now what? We want to rewrite this as $p|ab$, and the only natural way of doing this is $n^2+1 = (n+i)(n-i)$, which looks...somewhat illegal. But this is legal if we work in a ring that contains $i$, i.e. $\mathbb{Z}[i] = \{a+bi|a,b\in\mathbb{Z}\}$.

Let's prove that $\mathbb{Z}[i]$ is a Euclidean domain, so it will be a UFD. We need to write down a function $f$, and there's a fairly natural one that works: let $f(a+bi) = a^2+b^2$. Now, given $m,n \in \mathbb{Z}[i]$, the multiples of $m$ form a square lattice in $\mathbb{C}$ whose squares have side length $\sqrt{f(m)}$.

Then, our division/remainder condition boils down to the geometric fact that a point inside a square is at most $\frac{\sqrt{2}}2 < 1$ times the side of the square away from one of the vertices.

Great, so how do we use this fact? Let's look again at $p|n^2+1 = (n+i)(n-i)$. Suppose $p$ is irreducible in $\mathbb{Z}[i]$, then it's prime, so $p|(n+i)$ or $p|(n-i)$. This is obviously impossible since $\frac{n\pm i}p$ isn't of the form $a+bi$, $a,b\in \mathbb{Z}$. Alternatively, we could use the fact that $f$ is multiplicative: $f(mn) = f(m)f(n)$ (because for complex numbers, $|ab| = |a||b|$), so if $p|(n\pm i)$, then $f(p)|f(n\pm i)$, i.e. $p^2|p$, contradiction.

In other words, $p$ is not irreducible in $\mathbb{Z}[i]$(!), so there exists some (non-unit, non-$p$-times-unit) $a+bi$ such that $(a+bi)|p$. Then $f(a+bi)$ is a factor of $f(p) = p^2$ that isn't $1$ or $p^2$, so $f(a+bi)=p$, i.e. $a^2+b^2=p$.

A Diophantine equation

Here's a problem (slightly adapted) from my homework from when I was learning about UFDs:

Solve $x^2+2 = y^3$ in integers.

It's tempting to factorise the LHS, isn't it? We have $y^3 = (x+\sqrt{-2})(x-\sqrt{-2})$. For this to go anywhere, we need $\mathbb{Z}[\sqrt{-2}] = \{a + b\sqrt{-2}|a,b \in \mathbb{Z}\}$ to be a UFD. Indeed, it's a Euclidean domain by setting $f(a+ b\sqrt{-2}) = a^2+2b^2$; the same proof as in $\mathbb{Z}[i]$ holds by replacing the squares with rectangles of side ratio $1:\sqrt{2}$. Note that this $f$ is again multiplicative.

Now, it would be nice if the $x\pm\sqrt{-2}$ are coprime, so each term would be a square in $\mathbb{Z}[\sqrt{-2}]$. Well, their difference is $2\sqrt{-2} = -\sqrt{-2}^3$, which is a factorisation into irreducibles (since $f(\sqrt{-2}) = 2$ is a prime number). On the other hand, if $\sqrt{-2}|x$, then $x$ is even, so $y^3 = x^2+2$ is even, so a multiple of $8$, but then the RHS is $2 \pmod4$, contradiction. Hence, the $x\pm\sqrt{-2}$ are coprime, so we have (by unique factorisation) $x + \sqrt{-2} = (a + b\sqrt{-2})^3$ for some $a,b \in \mathbb{Z}$.

Expand the RHS and compare real and imaginary parts, so we have $x = a^3 - 6ab^2$ and $1 = 3a^2b - 2b^3 = b(3a^2 - 2b^2)$. The second equation immediately tells us $b = \pm 1$. The $b=1$ case gives $a=\pm 1$, while the $b=-1$ case gives us some $a \not\in\mathbb{Z}$. Hence, we have $x = a^3 - 6ab^2 = \pm 5$. Checking, this gives us the solutions $(x,y) = (\pm5, 3)$, which are the only solutions.

Exercise: primes that are 1 mod 3

Here's a problem from Zhao Yu's problem set:

Show that every prime of the form $3k+1$ can be written as $x^2+3y^2$ for integers $x,y$.

I'll sketch an outline; do try to fill in the details yourself!

• By quadratic reciprocity, $p|n^2+3$ for some $n$. (Edit: Jit Wu dug through some old textbook and found this trick due to Euler: $n = 2g^k + 1$, where $g$ is a primitive root, works. Cool.)
• The geometric proof doesn't work to show that $\mathbb{Z}[\sqrt{-3}]$ is a Euclidean domain (why?). In fact, $\mathbb{Z}[\sqrt{-3}]$ is not a UFD: $2\times 2 = (1+\sqrt{-3})(1-\sqrt{-3})$. (In particular, $2$ is an irreducible which is not a prime - can you see why? Hint: the fast way to see this is to use the fact that the $f$ we have been using is multiplicative.)
• However, if we let $\omega = \frac{1+\sqrt{-3}}2$, then $\mathbb{Z}[\omega]$ is a Euclidean domain (how does the geometric proof change? What is $f$?) and thus a UFD.
• There exist integers $a,b$ such that $f(a+b\omega) = p$. If $b$ is even, we're done (why?).
• Multiply $a+b\omega$ by units to get to something of the right form.

A brief remark on the second bullet point: $\mathbb{Z}[\sqrt{-3}]$ isn't a UFD, but for people who do number theory, it somehow isn't the right object to consider (roughly speaking, it's because the set of numbers of the form $a+b\sqrt{-3}$ which are roots of a monic integer polynomial isn't $\mathbb{Z}[\sqrt{-3}]$, but $\mathbb{Z}[\omega]$). As such, the usual non-example of a non-UFD is $\mathbb{Z}[\sqrt{-5}]$, in which $2\times 3 = (1+\sqrt{-5})(1-\sqrt{-5})$. By considering the squares of their magnitudes (as we have been doing in our other rings), we may show that all four terms there are irreducible, but not prime.

Geometry bashing

A key fact about UFDs is the following corollary of Gauss' lemma:

If $R$ is a UFD, then $R[X]$ is a UFD.

Thus, by induction, $\mathbb{Z}[X_1,\ldots,X_k]$ is a UFD for all $k$. This is important for geometry bashing, because (unless something has gone very wrong) all expressions are fractions of integer polynomials. You'll probably never have to use this fact in a proof, but knowing that integer polynomials (in however many variables) form a UFD is very useful for algebraic intuition and knowing when to avoid expanding things unnecessarily. I'll probably write about this more when (if) I write an introductory bashing post. 

Anyway, that's it for now. I hope you've enjoyed this little teaser of abstract algebra.