Euclidean Algorithm

Given two or more positive integers, the greatest common divisor (gcd), or highest common factor (hcf), is the largest positive integer that divides the numbers without a remainder.

If we are given the prime factorization of the numbers, 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 \geq 1$. 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, factorizing numbers is a very difficult problem, so instead we use the Euclidean Algorithm.

Technique

To find the greatest common divisor using the Euclidean Algorithm, we perform long division several times. Starting with a pair of numbers $(A, B)$, we obtain $A = Q\times B + R$, where $Q$ is the quotient and $0 \leq R < B$ is the remainder. We then repeat the sequence with the pair $(B, R)$.

As a concrete example, the following is the Euclidean Algorithm performed to calculate $\gcd( 16457, 1638 )$:

\begin{aligned} 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{aligned}

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) .$

Worked Examples

1. Show that if $\gcd(A,N)=1$, then $\gcd(A,B) = \gcd(A, BN)$.

Solution: Let $P$ be the set of primes that divide either $A$ or $B$. Let $P'$ be the set of primes that divide either $A$, $B$ or $N$. Let $r_i '$ be the exponent of $p_i '$ in the term $BN$. If $p_i ' \mid A$, then $p_i \not | N$, hence $r_i ' = r_i$, so $\min(q_i, r_i ' ) = \min (q_i, r_i)$. If $p_i ' \not | A$, then $q_i=0$, so $\min(q_i, r_i) = 0 = \min(q_i , r_i')$. Hence, $\gcd(A,B) = \gcd(A,BN)$.

2. (IMO '59) Prove that $\frac {21n+4} {14n+3}$ is irreducible for every natural number $n$.

Solution: $\frac {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{aligned} 21n+4 & = &1 \times (14n+3) & + &7n+1 \\ 14n+3 & = &2 \times (7n+1) & + &1\\ 7n+1 & = & (7n+1) \times 1 & + &0. \\ \end{aligned}

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

Learn math with members around the world on Brilliant.

Error
We encountered an error while talking to our servers. Refresh the page and try again in a few seconds. If the problem persists, please email us.