The World of Algorithms - Greatest Common Divisor

Use Euclid's Division Algorithm to find the GCD of $135$ and $225$.

Step 1: Since $225 > 135$, we apply the division lemma to $a = 225$ and $b = 135$: $225 = 135 \times 1 + 90$ Step 2: Since the remainder $90 \neq 0$, we apply the division lemma to the divisor $135$ and the remainder $90$: $135 = 90 \times 1 + 45$ Step 3: Since the remainder $45 \neq 0$, we apply the division lemma to $90$ and $45$: $90 = 45 \times 2 + 0$ Step 4: The remainder is now $0$, so our procedure stops. The divisor at this stage is $45$. Therefore, $GCD(135, 225) = 45$.

Euclid's algorithm reduces the problem of finding the GCD of large numbers to finding the GCD of progressively smaller numbers until the remainder is zero.

Find the GCD of $24$ and $36$ using the Prime Factorization method.

Step 1: Write the prime factorization of each number. $24 = 2 \times 2 \times 2 \times 3 = 2^3 \times 3^1$ $36 = 2 \times 2 \times 3 \times 3 = 2^2 \times 3^2$ Step 2: Identify the common prime factors and choose the lowest power of each: Common factor $2$: lowest power is $2^2$ Common factor $3$: lowest power is $3^1$ Step 3: Multiply these values: $GCD = 2^2 \times 3^1 = 4 \times 3 = 12$

The GCD is the product of the lowest powers of all common prime factors.

Given that $GCD(306, 657) = 9$, find the $LCM(306, 657)$.

We use the property: $GCD(a, b) \times LCM(a, b) = a \times b$ Substituting the given values: $9 \times LCM(306, 657) = 306 \times 657$ $LCM(306, 657) = \frac{306 \times 657}{9}$ $LCM(306, 657) = 34 \times 657$ $LCM(306, 657) = 22338$

This formula allows us to calculate the LCM directly if the GCD and the product of the two numbers are known.