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.

## Comments

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

See full formatting guide" %}

Sort by:

TopNewest7 months, 3 weeks ago

thanks ! a lot for posting such notes post some more on different topics

Log in to reply