Use Euclid’s division algorithm to find the HCF of

1651 and 2032

Euclid’s Division is a method for finding the HCF (highest common factor) of two given integers. According to Euclid’s Division Algorithm, For any two positive integers, ‘a’ and ‘b’, there exists a unique pair of integers ‘q’ and ‘r’ which satisfy the relation:

a = bq + r , 0 ≤ r ≤ b

Given integers 1651 and 2032. Clearly 2032>1651.

By applying division lemma

⇒ 2032 = 1651×1 + 381

Since remainder 0, applying division lemma on 1651 and 381

⇒ 1651 = 381×4 + 127

Since remainder 0, applying division lemma on 381 and 127

⇒ 381 = 127×3 + 0

Since remainder = 0,

∴ the HCF of 1651 and 2032 is 127.