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

By K Balaji|Updated : November 9th, 2022

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

Read Full Article

History of Euclids Division Algorithm

In Book VII of Euclid's Elements, statement 30 is the first instance of the lemma. It is covered in almost every book that discusses basic number theory.

Integers were added as a generalisation of the lemma in Jean Prestet's textbook Nouveaux Elemens de Mathematiques in 1681.

Summary:-

Using Euclids division algorithm, the HCF of 196 and 38220 is 196. According to the Euclid's Division lemma, if there are two positive numbers a and b, then there must also be two separate integers q and r that meet the criteria.

Related Questions:-