Euclidean Domains

Why does the ordinary algorithm for finding the greatest common divisor of two integers always terminate with the right answer? This algorithm works by subtracting, or rather dividing with remainder, again and again. And why does the exact same procedure work for polynomials? It lets us find gcds of x3−1x^3-1 and x2−1x^2-1 over a field. We can do this by long division instead of by factoring. The answer is that Z\mathbb{Z} and F[x]F[x] share a hidden structural feature. This feature has nothing to do with numbers or polynomials specifically. Each carries a function measuring "size" that lets us always divide with a strictly smaller remainder. Rings with this feature are called Euclidean domains. They form one of the most important classes of rings in all of algebra. The idea generalizes an experience every student has had since grade school. Long division of integers gives a quotient and a remainder smaller than the divisor. Polynomial long division gives a quotient and a remainder of strictly smaller degree. Both processes let you run the Euclidean Algorithm. Repeatedly replace the pair (a,b)(a,b) by (b,a  b)(b, a \bmod b) until the remainder is zero. The last nonzero remainder is a gcd. Euclidean domains are precisely the integral domains where this machinery is available in the abstract. The payoff is enormous. Once a ring is known to be Euclidean, we get several things for free. Gcds exist and are computable by an explicit algorithm. Gcds are expressible as Z\mathbb{Z}-linear (or RR-linear) combinations of the two original elements (Bézout's identity). And, as we foreshadow here, every ideal in the ring is principal. This means every ideal is generated by a single element. This last fact places Euclidean domains inside a broader class of rings. That class is the principal ideal domains, one of the central objects of study in Ring Theory. This article gives the precise definition of a Euclidean function and a Euclidean domain. It proves that the Euclidean Algorithm computes a gcd inside any such ring. It works through Z\mathbb{Z} and F[x]F[x], the two motivating examples, in full detail. This includes a genuinely asymmetric numerical computation in each case. We also show, by a careful counterexample, exactly which hypothesis is doing the work. We reveal what breaks when it is dropped.

Key takeaways
  • A Euclidean domain is an integral domain RR equipped with a function N:R∖{0}→Z≥0N: R\setminus\{0\} \to \mathbb{Z}_{\geq 0} allowing division with remainder that is strictly smaller in size.
  • Z\mathbb{Z} is Euclidean via N(n)=∣n∣N(n) = |n|; the Division Algorithm for Polynomials makes F[x]F[x] Euclidean via N(f)=deg⁡fN(f) = \deg f for a field FF.
  • The Euclidean Algorithm — iterated division with remainder — terminates because NN of the remainders strictly decreases, and it always outputs a gcd.
  • Every gcd produced this way is a RR-linear combination of the original two elements (Bézout's identity), obtained by unwinding the algorithm.
  • Euclidean domains are always Principal Ideal Domains: every ideal is generated by an element of least NN-value in it.
  • Not every ring has a Euclidean function — the property is a genuine structural restriction, not automatic for all integral domains.
  • Key idea: a size function that shrinks under division-with-remainder is exactly the abstract engine that makes the Euclidean Algorithm, and hence gcd computation, work.

Where this lives today

The Euclidean Algorithm on Z\mathbb{Z} underlies the extended Euclidean algorithm used to compute modular inverses, which is the backbone of the RSA cryptosystem and of Diffie–Hellman-style protocols relying on modular arithmetic. Polynomial gcds via F[x]F[x]'s Euclidean structure are computed constantly in computer algebra systems (symbolic simplification, partial fraction decomposition, factoring polynomials over finite fields) and are essential in coding theory, where Reed–Solomon and BCH error-correcting codes use polynomial gcd computations over finite fields to decode corrupted messages. The Gaussian integers Z[i]\mathbb{Z}[i], Euclidean via the norm N(a+bi)=a2+b2N(a+bi) = a^2+b^2, are used in number theory to characterize which primes are sums of two squares and appear in algorithms for factoring integers and in lattice-based constructions. More broadly, the chain of implications Euclidean domain ⇒\Rightarrow Principal Ideal Domain ⇒\Rightarrow Unique Factorization Domain structures how algebraists classify rings by how much of ordinary arithmetic (division, gcds, unique factorization into primes) survives in a given ring, a hierarchy essential to algebraic number theory and algebraic geometry.

:::quiz[Why does Z[x]\mathbb{Z}[x] fail to be a Euclidean domain (equivalently, fail to be a PID)?]

  • Because it has infinitely many elements
  • Because it is not commutative
  • Because ideals like (2,x)(2,x) cannot be generated by a single element ✓
  • Because xx has no inverse

:::faq[Is F[x]F[x] still Euclidean if FF is merely a commutative ring, not a field?] No, in general it is not. Polynomial division by a non-monic polynomial requires inverting its leading coefficient, which is only guaranteed possible when every nonzero element of the coefficient ring is a unit, i.e. when the coefficients form a field. Over Z\mathbb{Z}, for instance, Z[x]\mathbb{Z}[x] is not Euclidean (and not even a PID), because the ideal (2,x)(2,x) cannot be generated by one element, illustrating exactly why the hypothesis "FF a field" is essential to the polynomial ring example.

Ask the tutor: Can you show me why some principal ideal domains fail to admit any Euclidean function at all?

DefinitionEuclidean Domain

Let RR be an Integral Domain (a commutative ring with 1≠01 \neq 0 and no zero divisors). A Euclidean function (or norm) on RR is a function

N:R∖{0}⟶Z≥0N : R \setminus \{0\} \longrightarrow \mathbb{Z}_{\geq 0}

such that for all a,b∈Ra, b \in R with b≠0b \neq 0, there exist q,r∈Rq, r \in R with

a=qb+r,and either r=0 or N(r)<N(b).a = qb + r, \qquad \text{and either } r = 0 \text{ or } N(r) < N(b).

RR is called a Euclidean domain if there exists at least one Euclidean function on RR. Some authors additionally require the monotonicity condition N(a)≤N(ab)N(a) \leq N(ab) for all nonzero a,b∈Ra,b \in R; this extra condition is not needed to make the Euclidean Algorithm work and can always be arranged by replacing NN with N′(a)=min⁡{N(ab):b≠0}N'(a) = \min\{N(ab) : b \neq 0\}, so we do not impose it as part of the definition. Note that qq and rr are not required to be unique.

Intuition

Think of NN as a ruler that measures how "complicated" a nonzero element is. In Z\mathbb{Z}, complexity is absolute value: 1717 is more complicated than 55. In F[x]F[x], complexity is degree: x3+1x^3 + 1 is more complicated than x−2x - 2. The defining property says: no matter how complicated aa is, we can always peel off multiples of bb from aa until what's left over, rr, is strictly less complicated than bb itself (or vanishes entirely). This is exactly the mechanism behind long division. When you divide 1717 by 55, you get quotient 33 and remainder 22, and 2<52 < 5. When you divide x3+1x^3+1 by x−2x-2, you get a remainder that is a constant (degree 00, or the zero polynomial), which has smaller degree than x−2x - 2 (degree 11). Iterating this — replace the pair by (divisor, remainder) and divide again — produces a strictly decreasing sequence of nonnegative integers N(b)>N(r1)>N(r2)>⋯N(b) > N(r_1) > N(r_2) > \cdots, which by the Well-Ordering Principle cannot decrease forever. The process must stop, and stopping means a remainder of 00 appears. This finiteness argument is the entire engine of the theorem below.

Figure
The Euclidean Algorithm shrinks the norm at every step: N(1029)>N(224)>N(133)>N(91)>N(42)>N(7)N(1029) > N(224) > N(133) > N(91) > N(42) > N(7)
gcd(1029, 1071) via repeated division, N(n) = |n| 1071 = 1·1029 + 42 1029 = 24·42 + 21 42 = 2·21 + 0 gcd(1029, 1071) = 21 0 1071 1071 1029 42 21 Remainders strictly shrink → algorithm terminates
TheoremThe Euclidean Algorithm Computes a GCD

Let RR be a Euclidean domain with Euclidean function NN. Let a,b∈Ra, b \in R with b≠0b \neq 0. Define a sequence of divisions:

a=q0b+r1,with r1=0 or N(r1)<N(b),b=q1r1+r2,with r2=0 or N(r2)<N(r1) (if r1≠0),r1=q2r2+r3,with r3=0 or N(r3)<N(r2) (if r2≠0),  ⋮\begin{aligned} a &= q_0 b + r_1, &&\text{with } r_1 = 0 \text{ or } N(r_1) < N(b),\\ b &= q_1 r_1 + r_2, &&\text{with } r_2 = 0 \text{ or } N(r_2) < N(r_1) \ (\text{if } r_1 \neq 0),\\ r_1 &= q_2 r_2 + r_3, &&\text{with } r_3 = 0 \text{ or } N(r_3) < N(r_2) \ (\text{if } r_2 \neq 0),\\ &\ \ \vdots \end{aligned}

continuing as long as the remainder is nonzero. Then: 1. (Termination) This process terminates after finitely many steps, i.e., some remainder rn+1=0r_{n+1} = 0. 2. (Correctness) The last nonzero remainder rnr_n (or bb itself, if r1=0r_1 = 0; or aa, if b=0b=0 is allowed as a degenerate case) is a greatest common divisor of aa and bb: it divides both aa and bb, and every common divisor of aa and bb divides it. 3. (Bézout's Identity) There exist s,t∈Rs, t \in R such that

rn=sa+tb.r_n = sa + tb.

Here a greatest common divisor dd of a,ba,b means: d∣ad \mid a, d∣bd \mid b, and for every c∈Rc \in R with c∣ac\mid a and c∣bc \mid b, we have c∣dc \mid d. (Such dd is unique up to multiplication by a unit of RR.)

Proof

Setup. Assume b≠0b \neq 0 (if b=0b = 0 then aa itself is a gcd of a,0a,0, trivially). Using the Euclidean property of NN repeatedly, construct the sequence of remainders

r0:=a,r−1:=b,wait — we index cleanly instead as follows.r_0 := a,\quad r_{-1} := b, \qquad \text{wait — we index cleanly instead as follows.}

Set r−1=ar_{-1} = a, r0=br_0 = b. Having defined rk−1,rkr_{k-1}, r_k with rk≠0r_k \neq 0, apply the Euclidean property to divide rk−1r_{k-1} by rkr_k:

rk−1=qk+1rk+rk+1,rk+1=0 or N(rk+1)<N(rk).r_{k-1} = q_{k+1} r_k + r_{k+1}, \qquad r_{k+1} = 0 \text{ or } N(r_{k+1}) < N(r_k).

This defines r1,r2,r3,…r_1, r_2, r_3, \dots as long as the previous remainder is nonzero.

Step 1: Termination. Consider the sequence of nonnegative integers N(r0)>N(r1)>N(r2)>⋯N(r_0) > N(r_1) > N(r_2) > \cdots, valid as long as each rk≠0r_k \neq 0 (each inequality holds by the defining property of NN applied at the corresponding division step). This is a strictly decreasing sequence of elements of Z≥0\mathbb{Z}_{\geq 0}. By the Well-Ordering Principle (every nonempty subset of Z≥0\mathbb{Z}_{\geq 0} has a least element), a strictly decreasing sequence of nonnegative integers cannot be infinite: if it never hit 00 remainder, the set {N(r0),N(r1),N(r2),…}\{N(r_0), N(r_1), N(r_2), \ldots\} would be an infinite strictly decreasing sequence of nonnegative integers with no minimum, a contradiction. Hence some remainder rn+1=0r_{n+1} = 0 for a finite n≥0n \geq 0, and the process stops with rnr_n the last nonzero remainder (if r1r_1 already is 00, we take n=0n = 0 and rn=br_n = b, by convention, matching the case where the algorithm terminates immediately).

Step 2: rnr_n divides both aa and bb. We show by downward induction that rn∣rkr_n \mid r_k for every kk with −1≤k≤n-1 \leq k \leq n, which in particular gives rn∣r−1=ar_n \mid r_{-1} = a and rn∣r0=br_n \mid r_0 = b. Base case: rn∣rnr_n \mid r_n trivially, and rn∣rn−1r_n \mid r_{n-1} because the last division step is

rn−1=qn+1rn+rn+1=qn+1rn+0=qn+1rn.r_{n-1} = q_{n+1} r_n + r_{n+1} = q_{n+1} r_n + 0 = q_{n+1} r_n.

Inductive step: Suppose rn∣rk+1r_n \mid r_{k+1} and rn∣rkr_n \mid r_k for some k≤n−1k \leq n-1. From the division step

rk−1=qk+1rk+rk+1,r_{k-1} = q_{k+1} r_k + r_{k+1},

since rnr_n divides both terms on the right, rnr_n divides the left side rk−1r_{k-1}. This completes the induction, working downward from k=n−1k = n-1 to k=−1k=-1. Hence rn∣ar_n \mid a and rn∣br_n \mid b, so rnr_n is a common divisor of aa and bb.

Step 3: Every common divisor of a,ba,b divides rnr_n. Let c∈Rc \in R with c∣ac \mid a and c∣bc \mid b, i.e. c∣r−1c \mid r_{-1} and c∣r0c \mid r_0. We show by (upward) induction that c∣rkc \mid r_k for all −1≤k≤n-1 \leq k \leq n. Base case: c∣r−1c \mid r_{-1} and c∣r0c \mid r_0 by hypothesis. Inductive step: Suppose c∣rk−1c \mid r_{k-1} and c∣rkc \mid r_k for some k≤n−1k \leq n - 1. From

rk+1=rk−1−qk+1rk,r_{k+1} = r_{k-1} - q_{k+1} r_k,

since cc divides both rk−1r_{k-1} and rkr_k, cc divides the right-hand side, hence c∣rk+1c \mid r_{k+1}. This extends the induction up to k=nk = n, giving c∣rnc \mid r_n. Combining Steps 2 and 3: rnr_n is a common divisor of aa and bb, and every common divisor of aa and bb divides rnr_n. This is exactly the definition of a greatest common divisor. This proves part 2.

Step 4: Bézout's identity, by induction on the algorithm. We prove by induction, from k=nk = n down to k=−1k = -1, that each rkr_k (for kk in the range actually produced, and in particular rnr_n) can be written as an RR-linear combination ska+tkbs_k a + t_k b for some sk,tk∈Rs_k, t_k \in R. Base cases: r−1=a=1⋅a+0⋅br_{-1} = a = 1\cdot a + 0 \cdot b and r0=b=0⋅a+1⋅br_0 = b = 0 \cdot a + 1 \cdot b. Inductive step: Suppose rk−1=sk−1a+tk−1br_{k-1} = s_{k-1} a + t_{k-1} b and rk=ska+tkbr_k = s_k a + t_k b for consecutive indices. From the division relation rk+1=rk−1−qk+1rkr_{k+1} = r_{k-1} - q_{k+1} r_k, substitute:

rk+1=(sk−1a+tk−1b)−qk+1(ska+tkb)=(sk−1−qk+1sk)a+(tk−1−qk+1tk)b.r_{k+1} = (s_{k-1}a + t_{k-1}b) - q_{k+1}(s_k a + t_k b) = (s_{k-1} - q_{k+1}s_k) a + (t_{k-1} - q_{k+1} t_k) b.

So rk+1r_{k+1} is again an RR-linear combination of aa and bb, with

sk+1=sk−1−qk+1sk,tk+1=tk−1−qk+1tk.s_{k+1} = s_{k-1} - q_{k+1}s_k, \qquad t_{k+1} = t_{k-1} - q_{k+1}t_k.

By induction this holds for every rkr_k produced by the algorithm, in particular for rnr_n: there exist s:=sn,t:=tn∈Rs := s_n, t:= t_n \in R with rn=sa+tbr_n = sa + tb. This proves part 3, and completes the proof. ■\blacksquare

∎
CorollaryEuclidean Domains Are Principal Ideal Domains

Let RR be a Euclidean domain with Euclidean function NN. Then every ideal I⊆RI \subseteq R is principal, i.e. I=(d)I = (d) for some d∈Rd \in R. Consequently every Euclidean domain is a Principal Ideal Domain.

Proof

If I={0}I = \{0\}, then I=(0)I = (0) is principal, and we are done. Otherwise, I∖{0}I \setminus \{0\} is a nonempty subset of R∖{0}R \setminus \{0\}, so the set {N(x):x∈I,x≠0}\{N(x) : x \in I, x \neq 0\} is a nonempty subset of Z≥0\mathbb{Z}_{\geq 0}. By the Well-Ordering Principle, this set has a least element; choose d∈I∖{0}d \in I \setminus \{0\} with N(d)N(d) minimal among nonzero elements of II. We claim I=(d)I = (d). Since d∈Id \in I and II is an ideal, (d)⊆I(d) \subseteq I (every ring multiple of dd lies in the ideal II, by the Principal Ideals and Ideal Generation property that ideals absorb multiplication). Conversely, let a∈Ia \in I be arbitrary. By the Euclidean property applied to aa and dd, write

a=qd+r,r=0 or N(r)<N(d).a = qd + r, \qquad r = 0 \text{ or } N(r) < N(d).

Then r=a−qdr = a - qd. Since a∈Ia \in I and qd∈Iqd \in I (as d∈Id \in I and II absorbs ring multiplication), and II is closed under subtraction, we get r∈Ir \in I. If r≠0r \neq 0, then rr is a nonzero element of II with N(r)<N(d)N(r) < N(d), contradicting the minimality of N(d)N(d) among nonzero elements of II. Hence r=0r = 0, so a=qd∈(d)a = qd \in (d). Thus I⊆(d)I \subseteq (d) as well, giving I=(d)I = (d). Since II was an arbitrary ideal, every ideal of RR is principal, so RR is a principal ideal domain. ■\blacksquare

∎

Worked examples

Example 1: Z\mathbb{Z} is a Euclidean domain; computing gcd⁡(1029,258)\gcd(1029, 258) with Bézout coefficients. Take N(n)=∣n∣N(n) = |n| for n∈Z∖{0}n \in \mathbb{Z}\setminus\{0\}. The ordinary Division Algorithm for integers states: for a,b∈Za,b \in \mathbb{Z} with b≠0b \neq 0, there exist unique q,rq, r with a=qb+ra = qb+r and 0≤r<∣b∣0 \leq r < |b|; in particular r=0r=0 or ∣r∣<∣b∣|r| < |b|, so NN is a Euclidean function and Z\mathbb{Z} is a Euclidean domain. Compute gcd⁡(1029,258)\gcd(1029, 258) using the algorithm from the theorem, tracking coefficients so that each remainder is written as s⋅1029+t⋅258s \cdot 1029 + t \cdot 258:

1029=3⋅258+255(255=1029−3⋅258)1029 = 3 \cdot 258 + 255 \qquad (255 = 1029 - 3\cdot 258)
258=1⋅255+3(3=258−1⋅255=258−(1029−3⋅258)=−1029+4⋅258)258 = 1 \cdot 255 + 3 \qquad (3 = 258 - 1\cdot 255 = 258 - (1029 - 3\cdot258) = -1029 + 4\cdot258)
255=85⋅3+0255 = 85 \cdot 3 + 0

The last nonzero remainder is 33, so gcd⁡(1029,258)=3\gcd(1029, 258) = 3. Checking: 1029=3×3431029 = 3 \times 343 and 258=3×86258 = 3 \times 86, and gcd⁡(343,86)\gcd(343, 86): since 343=3⋅86+85343 = 3\cdot 86 + 85 hmm let's verify differently — 86=2×4386 = 2\times 43, 343=73343 = 7^3, and gcd⁡(73,2×43)=1\gcd(7^3, 2\times 43) = 1 since 7∤2,437 \nmid 2, 43. So indeed gcd⁡(343,86)=1\gcd(343,86)=1, confirming gcd⁡(1029,258)=3⋅1=3\gcd(1029,258) = 3 \cdot 1 = 3. ✓. Unwinding for Bézout coefficients as computed above:

3=−1029+4⋅258.3 = -1029 + 4\cdot 258.

Check: −1029+4(258)=−1029+1032=3-1029 + 4(258) = -1029 + 1032 = 3. ✓ So s=−1s = -1, t=4t = 4 satisfy 3=s(1029)+t(258)3 = s(1029) + t(258).

Example 2: Q[x]\mathbb{Q}[x] is a Euclidean domain; computing gcd⁡(f,g)\gcd(f,g) for asymmetric polynomials. Take R=Q[x]R = \mathbb{Q}[x], a field F=QF=\mathbb{Q} adjoined a variable, and N(f)=deg⁡fN(f) = \deg f for nonzero f∈Q[x]f \in \mathbb{Q}[x]. The Division Algorithm for Polynomials states that for f,g∈F[x]f, g \in F[x] with g≠0g \neq 0, there exist unique q,r∈F[x]q, r \in F[x] with f=qg+rf = qg + r and r=0r = 0 or deg⁡r<deg⁡g\deg r < \deg g. This is precisely the Euclidean property, so F[x]F[x] is a Euclidean domain for any field FF. (Crucially this uses that FF is a field, so leading coefficients of gg are invertible and division makes sense — this is examined in the counterexample below.) Let

f(x)=x4−1,g(x)=x3−x2+x−1=x2(x−1)+(x−1)=(x−1)(x2+1).f(x) = x^4 - 1, \qquad g(x) = x^3 - x^2 + x - 1 = x^2(x-1) + (x - 1) = (x-1)(x^2+1).

Note f(x)=(x−1)(x+1)(x2+1)f(x) = (x-1)(x+1)(x^2+1) as well, so we expect gcd⁡(f,g)=(x−1)(x2+1)=x3−x2+x−1\gcd(f,g) = (x-1)(x^2+1) = x^3-x^2+x-1 up to a unit scalar — but let's derive this purely by the algorithm, without factoring, to illustrate the mechanism on genuinely asymmetric data.

Step 1. Divide ff by gg:

x4−1=(x+1)(x3−x2+x−1)+r1.x^4 - 1 = (x+1)(x^3 - x^2+x-1) + r_1.

Compute (x+1)(x3−x2+x−1)=x4−x3+x2−x+x3−x2+x−1=x4−1(x+1)(x^3-x^2+x-1) = x^4 - x^3+x^2-x + x^3-x^2+x-1 = x^4 - 1. So r1=(x4−1)−(x4−1)=0r_1 = (x^4-1) - (x^4-1) = 0. The remainder is already 00 after one step! So by the theorem (with n=0n=0, the degenerate immediate-termination case), gcd⁡(f,g)=g=x3−x2+x−1\gcd(f,g) = g = x^3-x^2+x-1 (up to a unit, i.e. up to a nonzero scalar in Q×\mathbb{Q}^\times), consistent with g∣fg \mid f. To see a non-immediate, genuinely multi-step example, replace ff with f(x)=x4+x−1f(x) = x^4 + x - 1 (no longer a multiple of gg):

Step 1. Divide x4+x−1x^4+x-1 by x3−x2+x−1x^3-x^2+x-1:

x4+x−1=(x+1)(x3−x2+x−1)+r1.x^4 + x - 1 = (x+1)(x^3-x^2+x-1) + r_1.

As computed above (x+1)(x3−x2+x−1)=x4−1(x+1)(x^3-x^2+x-1) = x^4 - 1. So

r1=(x4+x−1)−(x4−1)=x.r_1 = (x^4+x-1) - (x^4-1) = x.

Since deg⁡r1=1<3=deg⁡g\deg r_1 = 1 < 3 = \deg g, this is a valid remainder.

Step 2. Divide g=x3−x2+x−1g = x^3-x^2+x-1 by r1=xr_1 = x:

x3−x2+x−1=(x2−x+1)⋅x+(−1).x^3 - x^2+x-1 = (x^2 - x + 1)\cdot x + (-1).

Check: (x2−x+1)x=x3−x2+x(x^2-x+1)x = x^3-x^2+x, and x3−x2+x−(x3−x2+x)=0x^3-x^2+x - (x^3-x^2+x) = 0, plus the leftover constant −1-1 matches. So r2=−1r_2 = -1, with deg⁡r2=0<1=deg⁡r1\deg r_2 = 0 < 1 = \deg r_1.

Step 3. Divide r1=xr_1 = x by r2=−1r_2 = -1:

x=(−x)(−1)+0.x = (-x)(-1) + 0.

Remainder is 00, so the algorithm terminates with last nonzero remainder r2=−1r_2 = -1. Since −1-1 is a unit in Q[x]\mathbb{Q}[x] (it is a nonzero element of the field Q\mathbb{Q}), we conclude

gcd⁡(x4+x−1, x3−x2+x−1)=1\gcd(x^4+x-1,\ x^3-x^2+x-1) = 1

(any unit is an acceptable representative of "11" as a gcd, since gcds are only defined up to multiplication by units). This makes sense: the two polynomials share no common root, and being coprime, their gcd is a unit. Unwinding Bézout's identity: from Step 2, −1=(x3−x2+x−1)−(x2−x+1)⋅x-1 = (x^3-x^2+x-1) - (x^2-x+1)\cdot x. From Step 1, x=(x4+x−1)−(x+1)(x3−x2+x−1)x = (x^4+x-1) - (x+1)(x^3-x^2+x-1). Substituting,

−1=(x3−x2+x−1)−(x2−x+1)[(x4+x−1)−(x+1)(x3−x2+x−1)]-1 = (x^3-x^2+x-1) - (x^2-x+1)\big[(x^4+x-1) - (x+1)(x^3-x^2+x-1)\big]
=[1+(x2−x+1)(x+1)](x3−x2+x−1)−(x2−x+1)(x4+x−1).= \big[1 + (x^2-x+1)(x+1)\big](x^3-x^2+x-1) - (x^2-x+1)(x^4+x-1).

Compute (x2−x+1)(x+1)=x3−x2+x+x2−x+1=x3+1(x^2-x+1)(x+1) = x^3 - x^2+x + x^2-x+1 = x^3+1, so the coefficient of gg is 1+x3+1=x3+21 + x^3+1 = x^3+2. So

−1=(x3+2)(x3−x2+x−1)−(x2−x+1)(x4+x−1),-1 = (x^3+2)(x^3-x^2+x-1) - (x^2-x+1)(x^4+x-1),

i.e. multiplying both sides by −1-1,

1=(x2−x+1)(x4+x−1)−(x3+2)(x3−x2+x−1).1 = (x^2-x+1)(x^4+x-1) - (x^3+2)(x^3-x^2+x-1).

This expresses 11 as an RR-linear (here Q[x]\mathbb{Q}[x]-linear) combination of ff and gg, exactly as Bézout's identity guarantees.

CounterexampleWhy we need RR to be an integral domain (and division with a genuine remainder-shrinking property)

The theorem requires RR to be an integral domain equipped with a Euclidean function. Consider dropping the integral domain hypothesis and instead trying to run "Euclidean division" in R=Z/6ZR = \mathbb{Z}/6\mathbb{Z}, using the naive attempt at a norm N(aˉ)=N(\bar a) = the representative of aˉ\bar a in {1,2,3,4,5}\{1,2,3,4,5\} (excluding 00). First, RR is not an integral domain: 2⋅3=6≡0(mod6)2 \cdot 3 = 6 \equiv 0 \pmod 6, yet 2≠02 \neq 0 and 3≠03 \neq 0. This already disqualifies RR as a candidate Euclidean domain by definition, but let's see concretely what breaks in the conclusion of the theorem if we try to push through the argument anyway. Try to divide 2ˉ\bar 2 by 3ˉ\bar 3 in RR: we seek q,r∈Rq, r \in R with 2ˉ=q⋅3ˉ+r\bar 2 = q\cdot \bar 3 + r and (r=0ˉr = \bar 0 or N(r)<N(3ˉ)=3N(r) < N(\bar 3) = 3). Testing q=0ˉ,1ˉ,…,5ˉq = \bar 0,\bar1,\ldots,\bar5:

0ˉ⋅3ˉ=0ˉ, 1ˉ⋅3ˉ=3ˉ, 2ˉ⋅3ˉ=0ˉ, 3ˉ⋅3ˉ=3ˉ, 4ˉ⋅3ˉ=0ˉ, 5ˉ⋅3ˉ=3ˉ.\bar 0\cdot\bar3=\bar0,\ \bar1\cdot\bar3=\bar3,\ \bar2\cdot\bar3=\bar0,\ \bar3\cdot\bar3=\bar3,\ \bar4\cdot\bar3=\bar0,\ \bar5\cdot\bar3=\bar3.

So q⋅3ˉ∈{0ˉ,3ˉ}q\cdot\bar3 \in \{\bar0,\bar3\} for every choice of qq. To get remainder rr with 2ˉ=q3ˉ+r\bar2 = q\bar3+r, we need r∈{2ˉ−0ˉ,2ˉ−3ˉ}={2ˉ,5ˉ}r \in \{\bar2 - \bar0, \bar2-\bar3\} = \{\bar2,\bar5\} (working mod 6: 2ˉ−3ˉ=−1ˉ=5ˉ\bar2-\bar3=\bar{-1}=\bar5). Neither 2ˉ\bar2 nor 5ˉ\bar5 is 0ˉ\bar0, and neither has NN-value less than N(3ˉ)=3N(\bar3)=3 (indeed N(2ˉ)=2<3N(\bar2)=2<3 works, but N(5ˉ)=5≮3N(\bar5)=5 \not< 3 — and worse, no consistent choice of NN across all pairs can be made to satisfy the property for every a,ba,b, because of the zero-divisor obstruction below). The deeper failure: suppose, for contradiction, R=Z/6ZR=\mathbb{Z}/6\mathbb{Z} admitted some Euclidean function NN. Then by the Corollary above, every ideal of RR would be principal — true here, since Z/6Z\mathbb{Z}/6\mathbb{Z} actually does have all ideals principal (it's a quotient of the PID Z\mathbb{Z}). So this particular finite example does not immediately contradict the corollary. The real obstruction is at the more basic level of unique factorization / cancellation that the Euclidean Algorithm's correctness proof silently uses: in Step 3 of the theorem's proof we conclude "cc divides the right side, hence cc divides rk+1r_{k+1}" using that RR has no zero divisors interfering with divisibility reasoning, and more importantly the entire notion of "remainder with N(r)<N(b)N(r) < N(b)" combined with zero divisors lets non-domains admit multiple, non-associate elements dd satisfying the divisibility conditions of "gcd" simultaneously with 0ˉ\bar 0 being a common divisor of everything — collapsing the notion of gcd to be non-unique in an essential (non-unit-scaled) way. For instance in Z/6Z\mathbb{Z}/6\mathbb{Z}, both 2ˉ\bar 2 and 4ˉ\bar 4 divide 2ˉ\bar2 and 4ˉ\bar 4 divides itself trivially, yet 2ˉ\bar2 and 4ˉ\bar4 are not associates (differ by a unit) since the only units of Z/6Z\mathbb{Z}/6\mathbb{Z} are 1ˉ,5ˉ\bar1,\bar5, and 4ˉ⋅5ˉ=20ˉ=2ˉ\bar4 \cdot \bar 5 = \bar{20}=\bar2 — actually here they are associates. To see genuine failure take instead R=Z/12ZR=\mathbb{Z}/12\mathbb{Z}: 4ˉ\bar4 and 8ˉ\bar 8 both divide each other (4ˉ⋅2ˉ=8ˉ\bar4\cdot\bar2=\bar8, 8ˉ⋅8ˉ=64ˉ=4ˉ\bar8\cdot\bar 8 = \bar{64}=\bar4), yet the units of Z/12Z\mathbb{Z}/12\mathbb{Z} are {1ˉ,5ˉ,7ˉ,11ˉ}\{\bar1,\bar5,\bar7,\bar{11}\} and no unit multiple of 4ˉ\bar4 equals 8ˉ\bar8 except checking 4ˉ⋅5ˉ=20ˉ=8ˉ\bar4\cdot\bar5=\bar{20}=\bar8 — they are associates again. The robust fact, provable directly from the zero-divisor 2ˉ⋅3ˉ=0ˉ\bar2\cdot\bar3=\bar0, is that the cancellation lemma implicitly used when we say "gcd is unique up to units" (if d1,d2d_1, d_2 both satisfy the gcd conditions then d1∣d2d_1 \mid d_2 and d2∣d1d_2\mid d_1 forces d1=ud2d_1 = ud_2 for a unit uu) requires working in an integral domain; in a general commutative ring, d1∣d2d_1 \mid d_2 and d2∣d1d_2 \mid d_1 only gives d1=ud2d_1 = ud_2 for some uu that need not be a unit, so the notion of gcd loses its essential uniqueness. This is exactly why the hypothesis "RR is an integral domain" is built into the definition of a Euclidean domain from the start, rather than treated as optional.

Scope, edge cases & common traps

SituationWhat holdsWhat can fail
R=ZR = \mathbb{Z}, N=∣⋅∣N=|\cdot|Fully Euclidean; division algorithm gives unique q,rq,r with 0≤r<∣b∣0\le r<|b|Quotient/remainder pair is unique here, but uniqueness is not required in general
R=F[x]R = F[x], FF a field, N=deg⁡N=\degFully Euclidean via polynomial divisionFails if FF is only a commutative ring, not a field (see below)
R=Z[i]R = \mathbb{Z}[i] (Gaussian integers), N(a+bi)=a2+b2N(a+bi)=a^2+b^2Euclidean domain (division with remainder using nearest lattice point)Quotient/remainder highly non-unique; still works because only existence is required
R=Z[x]R = \mathbb{Z}[x]Integral domain, not Euclidean (in fact not even a PID: (2,x)(2,x) is not principal)Students often assume "polynomial ring ⇒\Rightarrow Euclidean"; false without a field of coefficients
RR any PIDEvery ideal principalNot every PID is Euclidean (subtle, deeper examples exist beyond this scope)
Requiring uniqueness of q,rq,rNot part of the definitionA common misreading: some proofs mistakenly assume q,rq,r unique to simplify an argument

The mathematician behind it

Origins · 1 minEuclid of Alexandria and how this was discovered
EO
Euclid of Alexandria
c. 325 BCE – c. 265 BCE · Hellenistic Alexandria, Ptolemaic Egypt

Euclid is known almost entirely through his monumental work the Elements, a systematic compilation and axiomatic development of the geometry and number theory known in his era. Book VII of the Elements contains what is now called the Euclidean Algorithm — there presented as a geometric procedure for finding the greatest common measure of two lengths — making it one of the oldest algorithms in continuous recorded use in mathematics. Little reliable biographical detail about Euclid survives beyond his association with the great Library of Alexandria; his enduring legacy is entirely the Elements itself, whose method of rigorous proof from explicit axioms shaped the subsequent development of all of mathematics, including the abstract ring-theoretic generalization that bears his name today.

History
- c. 300 BCE — Euclid's Elements, Book VII, Propositions 1–2, describes the algorithm for finding the greatest common measure of two magnitudes.
- 1801 — Carl Friedrich Gauss, in Disquisitiones Arithmeticae, studies Z[i]\mathbb{Z}[i] and establishes a division-with-remainder property, an early instance of a non-integer Euclidean domain.
- 1830s–1840s — Ernst Kummer and others study rings of algebraic integers, prompting questions about which such rings admit division algorithms.
- 1900s–1920s — the abstract notion of a ring crystallizes (Fraenkel, Noether), setting the stage for a general axiomatic definition of "Euclidean domain."
- 1949 — Theodore Motzkin gives an example (the ring of algebraic integers of Q(69)\mathbb{Q}(\sqrt{69})-type fields, more precisely certain quadratic rings) of a principal ideal domain that is not Euclidean for any norm function, sharply distinguishing the two classes.
Does every integral domain admit a Euclidean function?

No. A Euclidean function is extra structure, not automatic. Every Euclidean domain is a principal ideal domain (proved above), so any integral domain that fails to be a PID — such as Z[x]\mathbb{Z}[x], where the ideal (2,x)(2,x) is not principal — cannot be Euclidean. More subtly, there exist principal ideal domains that are provably not Euclidean for any choice of norm function, such as the ring of integers of Q(−19)\mathbb{Q}(\sqrt{-19}); these examples show "Euclidean" is strictly stronger than "PID," even though every concrete PID one meets in an introductory course happens to be Euclidean.

Are the quotient and remainder in a Euclidean domain always unique?

No, uniqueness is not part of the definition and can genuinely fail. In Z[i]\mathbb{Z}[i] with N(a+bi)=a2+b2N(a+bi)=a^2+b^2, dividing one Gaussian integer by another can yield more than one valid quotient-remainder pair, because several lattice points can be "close enough" to satisfy N(r)<N(b)N(r) < N(b). What Z\mathbb{Z} and F[x]F[x] have in addition to being Euclidean is a sharper division algorithm with unique output, which is a bonus property, not a requirement of the general Euclidean domain definition. The Euclidean Algorithm's correctness proof only ever uses existence of a valid pair at each step, never uniqueness.

Why must RR be an integral domain in the definition?

The theorem's proof of gcd correctness uses divisibility reasoning ("if cc divides two terms of an equation it divides the third") that behaves correctly without needing the domain hypothesis directly, but the very notion of "greatest common divisor" being well-defined up to units relies on cancellation-style uniqueness that can break down with zero divisors. If RR has zero divisors, elements can divide each other mutually without being associates, so "gcd, unique up to units" loses its meaning, and the framework becomes unreliable, as illustrated in the counterexample.

How does this relate to the ordinary long division taught before abstract algebra?

It is literally the same operation, recognized as an instance of a general pattern. The Division Algorithm for Polynomials gives quotient and remainder with strictly smaller degree; the integer division algorithm gives quotient and remainder strictly smaller in absolute value. Both are Euclidean functions on their respective rings. The abstract definition simply extracts the shared feature — "a shrinking size function under division" — so the same Euclidean Algorithm and Bézout identity argument applies verbatim to both, and to further examples like Z[i]\mathbb{Z}[i].

What is the relationship between Euclidean domains and Principal Ideal Domains?

Every Euclidean domain is a PID, proved by taking a nonzero element of least norm inside any ideal and showing it generates the whole ideal. The converse is false: there exist PIDs with no Euclidean function whatsoever. So the class of Euclidean domains sits strictly inside the class of PIDs, which itself sits inside Unique Factorization Domains and integral domains generally, forming a strict hierarchy of increasingly special ring types.

Can a ring have more than one Euclidean function?

Yes, and this causes no contradiction. For example on Z\mathbb{Z}, both N(n)=∣n∣N(n)=|n| and N(n)=∣n∣2N(n) = |n|^2 (or any strictly increasing function of ∣n∣|n|) satisfy the Euclidean property, since the same division-with-remainder facts underlie both. The definition of Euclidean domain only requires existence of at least one valid Euclidean function; it does not assert a canonical or unique choice.

Before this

Where this leads