By using Euclid’s algorithm, find the largest number which divides 650 and 1170.

Question

Philoid · Accepted Answer

To find the largest number which divides 650 and 1170, we need to find the Highest Common Factor. According to Euclid’s Division Lemma, if a and b are any two positive integers then there exist two unique whole numbers q and r such that

a = b q + r,

where 0 ≤ r < b

Here, a is called the dividend,

b is called the divisor,

q is called the quotient and

r is called the remainder.

So, apply the lemma on 1170 and 650.

We get,

1170 = (650 × 1) + 520

Since the remainder is not zero.

Apply the lemma again on 650 and 520.

We get,

650 = (520 × 1) + 130

Since the remainder is not zero.

Apply the lemma again on 520 and 130.

We get,

520 = (130 × 4) + 0

We have finally got remainder as 0.

⇒ HCF (1170, 650) = 130

Therefore, the largest number which divides 1170 and 650 is 130.