Use Euclid’s Division Algorithm to Find the HCF of 196 and 38220

Using Euclids division algorithm, the HCF of 196 and 38220 is 196

Euclid’s Division Lemma states that if we have two positive integers a and b, then there must exist two distinct integers q and r that satisfy the requirement.

a = bq + r where 0 ≤ r < b

Euclid’s division lemma serves as the cornerstone of the Euclidean division algorithm. We employ Euclid’s division procedure to determine the Highest Common Factor (HCF) of two positive integers, a and b. The highest number that divides two or more positive integers precisely is known as the HCF. That indicates that the remainder is zero when the integers a and b are divided.

Consider the numbers 196 and 3820, and we need to determine their HCF.

Dividend = Quotient x Divisor + Remainder

When the reminder is zero then the quotient is the HCF.

Now 38220 > 196

Using Euclid’s division algorithm,

38220 = 196 x 195 + 0

Here, the remainder is 0.

Therefore, the HCF of 196 and 38220 is 196