krit.club logo

The World of Algorithms - Euclid's Algorithm for gcd

Grade 9CBSE

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

🔑Concepts

•

An algorithm is a series of well-defined steps which gives a procedure for solving a type of problem.

•

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

•

The Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), of two positive integers aa and bb is the largest positive integer dd that divides both aa and bb.

•

Euclid's Algorithm is a technique to compute the GCD of two large numbers by repeatedly applying the Division Lemma.

•

If GCD(a,b)=d\text{GCD}(a, b) = d, then dd also divides the remainder rr in the equation a=bq+ra = bq + r.

📐Formulae

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

GCD(a,b)=GCD(b,r)\text{GCD}(a, b) = \text{GCD}(b, r), where rr is the remainder when aa is divided by bb.

GCD(a,b)×LCM(a,b)=a×b\text{GCD}(a, b) \times \text{LCM}(a, b) = a \times b

💡Examples

Problem 1:

Use Euclid's algorithm to find the GCD of 455455 and 4242.

Solution:

We start with the larger integer, a=455a = 455, and the smaller integer, b=42b = 42.

Step 1: Apply Euclid's division lemma to 455455 and 4242: 455=42×10+35455 = 42 \times 10 + 35 Here, the remainder r=35r = 35, which is not 00.

Step 2: Now consider the divisor 4242 and the remainder 3535. Apply the lemma again: 42=35×1+742 = 35 \times 1 + 7 Here, the remainder r=7r = 7, which is not 00.

Step 3: Now consider the divisor 3535 and the remainder 77. Apply the lemma again: 35=7×5+035 = 7 \times 5 + 0 Since the remainder is now 00, the divisor at this stage is the GCD.

Therefore, GCD(455,42)=7\text{GCD}(455, 42) = 7.

Explanation:

The process involves replacing the larger number with the smaller number and the smaller number with the remainder of their division. This continues until the remainder becomes zero. The final non-zero divisor is the GCD.

Problem 2:

Find the HCF of 135135 and 225225 using the division algorithm.

Solution:

Since 225>135225 > 135, we apply the division lemma to 225225 and 135135:

Step 1: 225=135×1+90225 = 135 \times 1 + 90

Step 2: Since 90≠090 \neq 0, we apply the lemma to 135135 and 9090: 135=90×1+45135 = 90 \times 1 + 45

Step 3: Since 45≠045 \neq 0, we apply the lemma to 9090 and 4545: 90=45×2+090 = 45 \times 2 + 0

The remainder has become zero. The divisor at this stage is 4545.

Hence, the HCF of 135135 and 225225 is 4545.

Explanation:

At each step, we verify if the remainder is zero. If not, the current divisor becomes the new dividend and the current remainder becomes the new divisor.