Waste less time on Facebook — follow Brilliant.
×

Euclidean Algorithm

Shared by Calvin Lin 30, USA · 1 year, 4 months ago

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.

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](http://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \­( ... \­) or \­[ ... \­] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

See full formatting guide

Sort by:
Jun 20
Achal Jain
24, India

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

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...