Q. 1 F3.7( 3 Votes )

# Using Euclid’s division algorithm, find the HCF of

3318 and 4661

Answer :

Given numbers are 3318 and 4661

Here, 4661 > 3318

So, we divide 4661 by 3318

By using **Euclid’s division lemma**, we get

4661 = 3318 × 1 + 1343

Here, r = 1343 ≠ 0.

On taking 3318 as dividend and 1343 as the divisor and we apply Euclid’s division lemma, we get

3318 = 1343 × 2 + 632

Here, r = 632 ≠ 0

So, on taking 1343 as dividend and 632 as the divisor and again we apply Euclid’s division lemma, we get

1343 = 632 × 2 + 79

Here, r = 79 ≠ 0

So, on taking 632 as dividend and 79 as the divisor and again we apply Euclid’s division lemma, we get

632 = 79 × 8 + 0

The remainder has now become 0, so our procedure stops. Since the divisor at this last stage is 79, the **HCF of 3318 and 4661 is 79.**

Rate this question :

How useful is this solution?

We strive to provide quality solutions. Please rate us to serve you better.

Related Videos

Interactive Quiz:Euclid's Division Lemma44 mins

Fundamental Theorem of Arithmetic-238 mins

Champ Quiz | Fundamental Principle Of Arithmetic41 mins

Fundamental Theorem of Arithmetic- 143 mins

NCERT | Imp. Qs. on Rational and Irrational Numbers44 mins

Euclids Division Lemma49 mins

Quiz | Imp Qs on Real Numbers37 mins

Interactive Quiz - HCF and LCM32 mins

Application of Euclids Division Lemma50 mins

Relation Between LCM , HCF and Numbers46 mins

Try our Mini CourseMaster Important Topics in 7 DaysLearn from IITians, NITians, Doctors & Academic Expertsview all courses

Dedicated counsellor for each student

24X7 Doubt Resolution

Daily Report Card

Detailed Performance Evaluation