krit.club logo

The World of Algorithms - First Algorithm for gcd

Grade 9CBSE

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

🔑Concepts

•

GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two positive integers aa and bb is the largest positive integer that divides both aa and bb without leaving a remainder.

•

Euclid's Division Lemma: 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. Here, aa is the dividend, bb is the divisor, qq is the quotient, and rr is the remainder.

•

The Euclidean Algorithm is a systematic method for computing the GCDGCD of two numbers by repeatedly applying Euclid's Division Lemma.

•

The algorithm works on the principle that the GCDGCD of two numbers does not change if the larger number is replaced by its remainder when divided by the smaller number: GCD(a,b)=GCD(b,r)GCD(a, b) = GCD(b, r).

•

The process terminates when the remainder rr becomes 00. The divisor at this final stage is the GCD(a,b)GCD(a, b).

📐Formulae

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

GCD(a,b)=GCD(b,a(modb))GCD(a, b) = GCD(b, a \pmod b)

If r=0, then GCD(a,b)=b\text{If } r = 0, \text{ then } GCD(a, b) = b

💡Examples

Problem 1:

Find the GCDGCD of 135135 and 225225 using the Euclidean Algorithm.

Solution:

We start with the larger number a=225a = 225 and the smaller number b=135b = 135.

Step 1: Apply Euclid's Division Lemma to 225225 and 135135: 225=135×1+90225 = 135 \times 1 + 90 Here, the remainder r=90≠0r = 90 \neq 0.

Step 2: Apply the lemma to the previous divisor 135135 and the remainder 9090: 135=90×1+45135 = 90 \times 1 + 45 Here, the remainder r=45≠0r = 45 \neq 0.

Step 3: Apply the lemma to the previous divisor 9090 and the remainder 4545: 90=45×2+090 = 45 \times 2 + 0 Now the remainder is 00.

Since the remainder has become zero, the divisor at this stage is 4545. Therefore, GCD(135,225)=45GCD(135, 225) = 45.

Explanation:

We repeatedly divide the divisor by the remainder until the remainder becomes zero. The last non-zero remainder (or the final divisor) is the Greatest Common Divisor.

Problem 2:

Use Euclid's Algorithm to find the GCDGCD of 455455 and 4242.

Solution:

Step 1: 455=42×10+35455 = 42 \times 10 + 35 Step 2: 42=35×1+742 = 35 \times 1 + 7 Step 3: 35=7×5+035 = 7 \times 5 + 0

The remainder is now 00. The last divisor is 77. Thus, GCD(455,42)=7GCD(455, 42) = 7.

Explanation:

The algorithm systematically reduces the size of the numbers while maintaining the same common divisors until the GCDGCD is explicitly revealed as the final divisor.