Maths WorkshopMaths problems with full solutions
Exercise 1654Number theory › Divisibility and gcdOlympiadAdded 3 Nov 2026

GCD in $\mathbb{Z}$ vs $\mathbb{R}[X]$

#analogy#gcd#polynomials#integers

Statement

Draw a parallel between the Euclidean algorithms in Z\mathbb{Z} and in R[X]\mathbb{R}[X], and show that Bézout's identity holds in both rings.

Hint

The Euclidean algorithm is the same abstract procedure: replace (a,b)(a,b) by (b,r)(b,r) where rr is the remainder of aa divided by bb.

Show solutionHide solution

Solution

Common structure. Both Z\mathbb{Z} and R[X]\mathbb{R}[X] are Euclidean domains: for a,ba,b with b≠0b\neq0, there exist q,rq,r with a=bq+ra=bq+r and ν(r)<ν(b)\nu(r)<\nu(b) for some size function ν\nu (absolute value in Z\mathbb{Z}, degree in R[X]\mathbb{R}[X]).

Bézout. The Euclidean algorithm produces u,vu,v with au+bv=d=gcd⁡(a,b)au+bv=d=\gcd(a,b) in both rings.

Differences. In Z\mathbb{Z}, gcd⁡\gcd is positive by convention; in R[X]\mathbb{R}[X], gcd⁡\gcd is monic by convention. Units differ: {±1}\{\pm1\} vs R∗\mathbb{R}^*.

Conclusion. The Euclidean algorithm and Bézout's identity hold in any Euclidean domain, of which Z\mathbb{Z} and R[X]\mathbb{R}[X] are examples.