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

By BYJU'S Exam Prep

Updated on: September 25th, 2023

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

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.


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:-

SSC & Railway

Our Apps Playstore
SSC and Bank
Other Exams
GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303
Home Practice Test Series Premium