Back to the on-screen lesson ·
A ring with a division algorithm: the size function that forces a remainder to shrink, the algorithm it runs, and why it makes every ideal principal.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to state what a size function and a division algorithm are, verify that the integers, polynomials over a field and the Gaussian integers are Euclidean, run the Euclidean algorithm and write a greatest common divisor as a combination, say why uniqueness of the quotient is not required, find the division that fails in $\mathbb{Z}[x]$, and prove that every Euclidean domain is a principal ideal domain.
School arithmetic divides integers with a remainder; the first algebra course divides polynomials with a remainder of smaller degree. They were taught years apart and look nothing alike. This lesson names the one property they share — a size that the remainder is forced to shrink — and shows that every consequence either of them has follows from that alone.
A size function on an integral domain $R$ is a map $\delta$ from the non-zero elements to the non-negative integers. $R$ is a Euclidean domain for $\delta$ when for all $a$ and non-zero $b$ there exist $q, r$ with $a = qb + r$ and either $r = 0$ or $\delta(r) < \delta(b)$. A greatest common divisor of $a$ and $b$ is a common divisor divisible by every common divisor; it is unique up to associates.
The definition. An integral domain $R$ is Euclidean when there is a function $\delta$ from $R \setminus \{0\}$ to the non-negative integers such that for every $a \in R$ and every non-zero $b \in R$ there are $q, r \in R$ with
$$a = qb + r, \qquad r = 0 \ \text{ or } \ \delta(r) < \delta(b).$$
That is all. Nothing is required about uniqueness of $q$ and $r$, and nothing about $\delta$ beyond that it lands in a well-ordered set.
The three examples.
| Ring | Size function | Why it works |
|---|---|---|
| $\mathbb{Z}$ | $\lvert a \rvert$ | ordinary division with remainder |
| $F[x]$, $F$ a field | $\deg f$ | long division; the field supplies the inverses |
| $\mathbb{Z}[i]$ | $a^{2} + b^{2}$ | round the exact complex quotient to the nearest lattice point |
The last deserves a word. Given $a$ and $b \ne 0$, compute $a/b$ in $\mathbb{C}$ and round each coordinate to the nearest integer, getting $q$. Then $\lvert a/b - q \rvert^{2} \le (1/2)^{2} + (1/2)^{2} = 1/2$, so $N(a - qb) \le N(b)/2 < N(b)$. Every point of the plane is within distance $1$ of a lattice point, and that geometric fact is the division algorithm.
What follows.
The Euclidean algorithm. Divide, keep the remainder, repeat with the divisor and the remainder. The sizes strictly decrease so it terminates, and the last non-zero remainder is a greatest common divisor. Substituting backwards writes it as a combination.
What the definition does not give. Uniqueness of $q$ and $r$ is not part of it and genuinely fails in $\mathbb{Z}[i]$, where two lattice points can be equally close. And the converse of result 1 is false: $\mathbb{Z}\!\left[\frac{1 + \sqrt{-19}}{2}\right]$ is a principal ideal domain admitting no size function at all.
Another way: picture
A size function is a ruler, and the division algorithm is the promise that whatever you divide by, the bit left over is always shorter than what you divided by. That single promise makes any descending process terminate — which is why an algorithm that would otherwise run for ever comes to a stop, and why a set with no smallest member cannot hide inside an ideal.
Another way: steps
To show a ring is Euclidean: 1. Propose a size function into the non-negative integers. 2. Given $a$ and non-zero $b$, produce $q$ explicitly — by rounding, by long division, by whatever the ring offers. 3. Check the remainder $a - qb$ is zero or strictly smaller. To show it is not: 4. Find one division that cannot be done — in $\mathbb{Z}[x]$, dividing $x$ by $2$. 5. Or show unique factorisation fails, which rules out Euclidean at a stroke.
This unit is organised around one chain:
$$\text{Euclidean} \ \Longrightarrow\ \text{principal ideal domain} \ \Longrightarrow\ \text{unique factorisation domain} \ \Longrightarrow\ \text{integral domain}.$$
Each arrow is a real theorem and none of them reverses. The counterexamples are worth knowing by name, because they are what stop the four conditions being one condition under four names.
Euclidean but the algorithm is not unique. $\mathbb{Z}[i]$, where the nearest lattice point may be a tie. The definition tolerates this.
A PID that is not Euclidean. $R = \mathbb{Z}\!\left[\frac{1 + \sqrt{-19}}{2}\right]$. Every ideal is principal, but no size function exists: the proof shows that any Euclidean ring with only $\pm 1$ as units must have an element behaving like $2$ or $3$ modulo the ideal it generates, and this ring has none.
A UFD that is not a PID. $\mathbb{Z}[x]$. Factorisation is unique by Gauss's lemma, and $(2, x)$ needs two generators: a single generator $f$ would divide $2$, forcing $f = \pm 1$ or $\pm 2$, and would divide $x$, ruling out $\pm 2$ — but $(2, x)$ is not the whole ring, since its elements all have even constant term.
A domain that is not a UFD. $\mathbb{Z}[\sqrt{-5}]$, with its two factorisations of $6$.
A useful heuristic: a Euclidean structure is a computational gift — it hands over an algorithm — while being a PID is a structural statement about ideals. Most things one wants follow from the structural statement, which is why the second arrow failing to reverse costs little in practice.
Expecting the quotient and remainder to be unique. Not required, and false in $\mathbb{Z}[i]$. Only the existence matters.
Using the degree on $\mathbb{Z}[x]$. There is no way to divide $x$ by $2$ inside $\mathbb{Z}[x]$, so the algorithm fails at the first step. Polynomial division needs the coefficients to form a field.
Taking the last quotient as the gcd. It is the last non-zero remainder.
Assuming every PID is Euclidean. The implication runs one way, and the standard counterexample is a real ring rather than a technicality.
Thinking a size function must be a norm. Any map to the non-negative integers will do, provided the division property holds; different size functions on the same ring are fine.
Forgetting that $\delta$ is defined only on non-zero elements. $\delta(0)$ is not needed, and the case $r = 0$ is handled separately in the definition for exactly that reason.
Divide $11 + 3i$ by $1 + 2i$. In $\mathbb{C}$: $\dfrac{11 + 3i}{1 + 2i} = \dfrac{(11+3i)(1-2i)}{5} = \dfrac{17 - 19i}{5} = 3.4 - 3.8i$.
Compute the exact complex quotient.
Round each coordinate: $q = 3 - 4i$. Then $qb = (3 - 4i)(1 + 2i) = 11 + 2i$, so $r = (11 + 3i) - (11 + 2i) = i$.
Round to the nearest lattice point.
$N(r) = 1$ and $N(b) = 5$, so the remainder is smaller and the division is valid.
The remainder shrank.
In $\mathbb{Q}[x]$, apply the algorithm to $x^{3} - 1$ and $x^{2} - 1$: $x^{3} - 1 = x(x^{2} - 1) + (x - 1)$.
First division.
Then $x^{2} - 1 = (x + 1)(x - 1) + 0$, so the last non-zero remainder is $x - 1$.
The algorithm stops.
Reading the first line backwards: $x - 1 = 1 \cdot (x^{3} - 1) - x(x^{2} - 1)$, a combination of the two originals — which also says $(x^{3}-1, x^{2}-1) = (x - 1)$.
The gcd, and the ideal it generates.
Try the hardest case: divide $x$ by the constant $2$.
Pick a division to test.
A valid answer needs $x = 2q + r$ with $r = 0$ or $\deg r < \deg 2 = 0$, so $r$ would have to be zero — and $x = 2q$ has no solution in $\mathbb{Z}[x]$.
No quotient exists.
So the degree does not make $\mathbb{Z}[x]$ Euclidean. In fact no size function does, because $\mathbb{Z}[x]$ is not even a principal ideal domain: $(2, x)$ needs two generators.
Run the Euclidean algorithm on $84$ and $30$. The two numbers being divided are given on each line; fill in the quotient and the remainder.
| Divide this | By this | Quotient | Remainder | |
|---|---|---|---|---|
| First line | 84 | 30 | ||
| Second line | 30 | 24 | ||
| Third line | 24 | 6 |
Does this pair make a Euclidean domain: $\mathbb{Z}[\sqrt{2}]$ with $|a^{2} - 2b^{2}|$?
In $F[x]$ over a field, a polynomial of degree $6$ is divided by one of degree $2$. What is the largest degree the remainder can have?
Answer:
Select every statement that is true of a Euclidean domain.
This task has no paper form; do it on a device.
Put in order the steps of finding a greatest common divisor in a Euclidean domain.
Number the steps in order (write the number in the box):
Build the proof that every Euclidean domain is a principal ideal domain.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
In $F[x]$ over a field, a polynomial of degree $5$ is divided by one of degree $4$. What is the largest degree the remainder can have?
Answer:
You can run the Euclidean algorithm in a ring with a size function and say what the algorithm's termination depends on. Say in your own words why polynomial division needs the coefficients to form a field. Next: the structural condition the algorithm produced, taken as a hypothesis in its own right.
9. Your turn: is $\mathbb{Z}[x]$ Euclidean for the degree?, step 3