Euclidean Algorithm

The Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, without explicitly factoring the two integers.

It is used in countless applications, including computing the explicit expression in Bezout's identity, constructing continued fractions, reduction of fractions to their simple forms, and attacking the RSA cryptosystem. Furthermore, it can be extended to other rings that have a division algorithm, such as the ring \( {\mathbb Q}[x]\) of polynomials with rational coefficients.

The Euclidean algorithm solves the problem:

Given integers \(a,b,\) find \( d=\text{gcd}(a,b).\)

If the prime factorizations of \(a\) and \(b\) are known, finding the greatest common divisor is straightforward. Let \( a = p_1 ^{q_1} p_2 ^ {q_2} \ldots p_n^{q_n}\) and \( b= p_1 ^{r_1} p_2 ^ {r_2} \ldots p_n^{r_n}\), where \(p_i\) are positive prime integers and \( q_i, r_i\geq 0 \). Then

\[ \gcd{(a,b)} = p_1 ^ { \min(q_1, r_1)} p_2 ^ {\min (q_2, r_2)} \ldots p_n^{\min (q_n, r_n) }.\]

However, in general, factoring integers is a difficult problem from a computational perspective. The Euclidean algorithm provides a fast way to determine \(d\) without knowing the prime factors of \(a\) or \(b.\) Here is an outline of the steps:

1. Let \( a = x,\) \( b=y.\)
2. Given \(x,y\), use the division algorithm to write \(x=yq+r,\) \( 0\le r < |y|.\)
3. If \( r=0,\) stop and output \( y;\) this is the gcd of \(a,b.\)
4. If \( r\ne 0,\) replace \( (x,y) \) by \( (y,r).\) Go to step 2.

What is \( \gcd( 16457, 1638 )?\)

---

Apply the Euclidean algorithm:

\[ \begin{array}{rrl} 16457 =& 1638 \times 10 & + 77 \\ 1638 =& 77 \times 21 & + 21\\ 77 =& 21 \times 3 &+ 14 \\ 21 =& 14 \times 1 & + 7\\ 14 =& 7 \times 2 &+ 0. \end{array} \]

The process stops since we reached \(0,\) and we obtain

\[ 7 = \gcd (7, 14) = \gcd(14, 21) = \gcd (21, 77) = \gcd (77, 1638) = \gcd( 1638, 16457) . \ _\square\]

The last line of the above example suggests a proof that the Euclidean algorithm computes the gcd. That is, it is enough to show that the gcd of each pair of numbers in the algorithm is the same, because the last pair is \( (x,y)\) with \( y|x\), so \(\text{gcd}(x,y)=y,\) which is what the Euclidean algorithm outputs for \( \text{gcd}(a,b).\) Here is a proof of this statement:

Suppose \( a=bq+r.\) If \( d|a,d|b,\) then \(d|r,\) so \( \text{gcd}(a,b) \le \text{gcd}(b,r).\) But if \(e|b,e|r,\) then \(e|a,\) so \( \text{gcd}(b,r) \le \text{gcd}(a,b).\) So the GCDs are equal. \(_\square\)

(IMO '59) Prove that \( \dfrac {21n+4} {14n+3} \) is irreducible for every positive integer \( n\).

---

\( \dfrac {21n+4} {14n+3} \) is irreducible if and only if the numerator and denominator have no common factor, i.e. their greatest common divisor is 1. Applying the Euclidean algorithm,

\[ \begin{array}{rll} 21n+4 =& 1 \times (14n+3) &+7n+1 \\ 14n+3 =& 2 \times (7n+1) &+1\\ 7n+1 =& (7n+1) \times 1 & +0. \end{array} \]

Hence, \( \gcd(21n+4, 14n+3) =1\), which shows that the fraction is irreducible. \(_\square\)

Bezout's identity says that the equation \( ax+by=\text{gcd}(a,b)\) has solutions \(x,y.\) The Euclidean algorithm gives a method for finding one pair of solutions.

Find integers \(x,y\) such that \( 16457x+1638y = 7.\)

---

Reverse the Euclidean algorithm:

\[ \begin{align} 16457 &= 1638 \times 10 + 77 \\ 1638 &= 77 \times 21 + 21\\ 77 &= 21 \times 3 + 14 \\ 21 &= 14 \times 1 + 7\\ 14 &= 7 \times 2 + 0. \end{align} \]

Express \(7\) as a linear combination of numbers moving up the line:

\[ \begin{align} 7&= 21- 1\cdot 14 \\ &= 21-1(77-21\cdot 3)= 21\cdot 4-77 \cdot 1 \\ &= (1638-77\cdot 21)4 - 77 \cdot 1 = 1638 \cdot 4- 77 \cdot 85 \\ &= 1638 \cdot 4 - (16457-1638\cdot 10)85 =16457(-85)+1638\cdot 854. \end{align} \]

So \(x=-85,y=854\) is a solution. \(_\square\)

See the Extended Euclidean Algorithm wiki for more details.

The Euclidean algorithm can be used in any ring with a division algorithm. Here are two examples:

Find the GCD of the polynomials \( x^5 + x^4 + 2x^3 + 2x^2 + 2x + 1\) and \(x^5 + x^4 + x^3 - x^2 - x - 1\) over \( \mathbb Q.\)

---

Use Euclidean algorithm:

\[ \begin{align} x^5+x^4+2x^3+2x^2+2x+1 &= (x^5+x^4+x^3-x^2-x-1)1 + (x^3+3x^2+3x+2) \\ x^5+x^4+x^3-x^2-x-1 &= (x^3+3x^2+3x+2)(x^2-2x+4)+(-9x^2-9x-9) \\ x^3+3x^2+3x+2 &= (-9x^2-9x-9)\left( -\frac19x-\frac29\right) + 0. \end{align} \]

So "the" GCD is \(-9x^2-9x-9.\) See below for a comment on uniqueness. \(_\square\)

In a ring with a division algorithm (sometimes called a Euclidean ring), the GCD is defined up to multiplication by a unit, i.e. an element of the ring with a multiplicative inverse. The units in the ring \( \mathbb Z\) of integers are \( \pm 1,\) so this ambiguity is resolved by stipulating that the GCD is positive. In \( F[x]\) where \( F\) is a field, the units are the nonzero constant polynomials. For instance, in the above example, \(-9x^2-9x-9\) divides every common divisor of the two polynomials, but so does \( 9x^2+9x+9\) or \( \frac1{100}x^2+\frac1{100}x+\frac1{100}\) or any other constant multiple of \( -9x^2-9x-9.\) This ambiguity can be resolved here by stipulating that the GCD should always be a monic polynomial—in this case \( x^2+x+1.\)

Find \( \text{gcd}(4+17i,7+6i)\) in the Gaussian integers \( {\mathbb Z}[i].\)

---

Use the Euclidean algorithm:

\[ \begin{align} 4+17i &= (7+6i)(2+i)+(-4-2i) \\ 7+6i &= (-4-2i)(-2)+(-1+2i) \\ -4-2i &= (-1+2i)(2i)+0. \end{align} \]

So "the" GCD is \( -1+2i.\) Note that the units in \( {\mathbb Z}[i]\) are \( \pm 1, \pm i,\) so there are four equally valid answers: \( -1+2i, 1-2i, -2-i, 2+i.\) \(_\square\)

Note that the division algorithm quotients above are obtained by dividing and rounding to the nearest Gaussian integer, e.g.

\[ \frac{4+17i}{7+6i} = \frac{(4+17i)(7-6i)}{(7+6i)(7-6i)} = \frac{130+95i}{85}, \]

which is closest to \( 2+i.\)