krit.club logo

The World of Algorithms - Finding the Greatest Common Divisor

Grade 9CBSE

Review the key concepts, formulae, and examples before starting your quiz.

🔑Concepts

•

The Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), of two or more positive integers is the largest positive integer that divides each of the integers without leaving a remainder.

•

Euclid's Division Lemma states that for any two positive integers aa and bb, there exist unique integers qq and rr such that a=bq+ra = bq + r, where 0≤r<b0 \le r < b.

•

Euclid's Division Algorithm is a step-by-step procedure to find the HCF of two numbers. It involves repeated application of the Division Lemma until the remainder becomes zero.

•

The Fundamental Theorem of Arithmetic states that every composite number can be expressed as a product of primes, and this factorization is unique apart from the order of the factors.

•

Using Prime Factorization: The HCF is the product of the smallest power of each common prime factor in the numbers.

•

Property: For any two positive integers aa and bb, the product of their HCF and LCM is equal to the product of the numbers themselves.

📐Formulae

a=bq+r, where 0≤r<ba = bq + r, \text{ where } 0 \le r < b

HCF(a,b)×LCM(a,b)=a×bHCF(a, b) \times LCM(a, b) = a \times b

HCF(a,b,c)=HCF(a,HCF(b,c))HCF(a, b, c) = HCF(a, HCF(b, c))

💡Examples

Problem 1:

Find the HCF of 455455 and 4242 using Euclid's Division Algorithm.

Solution:

We apply Euclid's division lemma to 455455 and 4242:

  1. Since 455>42455 > 42, we write: 455=42×10+35455 = 42 \times 10 + 35 Here, the remainder r=35≠0r = 35 \ne 0.

  2. Now, we apply the lemma to the divisor 4242 and the remainder 3535: 42=35×1+742 = 35 \times 1 + 7 Here, the remainder r=7≠0r = 7 \ne 0.

  3. Next, we apply the lemma to 3535 and 77: 35=7×5+035 = 7 \times 5 + 0 Now, the remainder is 00. The divisor at this stage is 77.

Therefore, HCF(455,42)=7HCF(455, 42) = 7.

Explanation:

Euclid's algorithm works by replacing the larger number with the remainder of the division until the remainder is zero. The last non-zero remainder (or the divisor when remainder is zero) is the HCF.

Problem 2:

Find the HCF of 9696 and 404404 by the prime factorization method. Hence, find their LCM.

Solution:

First, find the prime factors of 9696 and 404404: 96=25×3196 = 2^5 \times 3^1 404=22×1011404 = 2^2 \times 101^1

To find the HCF, take the product of the lowest powers of common factors: Common factor is 22, and the lowest power is 222^2. HCF(96,404)=22=4HCF(96, 404) = 2^2 = 4

Now, use the relationship HCF×LCM=a×bHCF \times LCM = a \times b: 4×LCM=96×4044 \times LCM = 96 \times 404 LCM=96×4044LCM = \frac{96 \times 404}{4} LCM=96×101LCM = 96 \times 101 LCM=9696LCM = 9696

Explanation:

The prime factorization method identifies the building blocks of the numbers. The HCF uses common blocks, while the LCM uses all blocks at their highest powers.

Problem 3:

Use the division method to show the calculation of HCF for 135135 and 225225.

Solution:

Performing vertical division steps: 1135)225‾−13590\begin{array}{r} 1 \\ 135 \overline{) 225} \\ -135 \\ \hline 90 \end{array} Now 9090 becomes the divisor and 135135 the dividend: 190)135‾−9045\begin{array}{r} 1 \\ 90 \overline{) 135} \\ -90 \\ \hline 45 \end{array} Finally, 4545 becomes the divisor and 9090 the dividend: 245)90‾−900\begin{array}{r} 2 \\ 45 \overline{) 90} \\ -90 \\ \hline 0 \end{array} The last divisor is 4545, so HCF(135,225)=45HCF(135, 225) = 45.

Explanation:

The long division method for HCF is a visual representation of Euclid's Algorithm where each remainder becomes the new divisor for the previous divisor.