Waste less time on Facebook — follow Brilliant.
×

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.

Note by Calvin Lin
2 years, 8 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

thanks ! a lot for posting such notes post some more on different topics Achal Jain · 1 year, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...