Question

use euclid division algorithm find the hcf of50&60​

Answer 1

Answer:

filledbookmark

USE APP

Sign in

Questions & Answers

CBSE

Mathematics

Grade 10

Euclid's Division Algorithm

Question

Answers

Related Questions

Use Euclid's division algorithm to find the HCF of 726 and 275.

Answer

VerifiedVerified

29.7K+ Views

2 Likes

Hint: Use the step by step procedure of Euclid's division algorithm using the division lemma. Hence find the largest number exactly dividing the two numbers which is the HCF of the two numbers.

Complete step-by-step answer:

The largest positive integer which divides two or more integers without any remainder is called Highest Common Factor (HCF) or Greatest Common Divisor or Greatest Common Factor (GCF).

We can find the HCF of two numbers using Euclid’s division algorithm.

Euclid’s division algorithm: This is based on Euclid’s division lemma. According to this, the HCF of any two positive integers a and b, with a>b, is obtained as follows:

Step 1: Apply the division lemma to find q and r where a=bq+r ,0⩽r<b.

Step 2: if r=0, the HCF is b. If r≠0, apply Euclid’s lemma to b and r.

Step 3: Continue the process till the remainder is zero. The divisor at this stage will be the HCF of aand b.

Given the problem, we need to find HCF of 726 and 175 using Euclid's division algorithm.

Using the above steps with a=726 and b=275 because 726>275, hence a>b.

Using division lemma on a=726, we get

726=bq+r=275×2+176⇒b=275,q=2,r=176

Since r≠0, applying Euclid’s lemma to b and r, we get

275=176×1+99⇒b=275,q=1,r=99

Again, since r≠0, applying Euclid’s lemma to b and rand continuing the same step till we get r=0.

176=99×1+7799=77×1+2277=22×3+1122=11×2+0=bq+r⇒b=11,q=2,r=0

Since for b=11, we get the remainder r=0.

Hence by Euclid’s division algorithm, 11 is the HCF of 726 and 275.

Answer 2

Answer :

By this example u can do it urself for ur better knowledge :) If u don't do it by urself u not gonna understand any thing ...

(i) 135 and 225

Step 1: First find which integer is larger.

225>135

Step 2: Then apply the Euclid's division algorithm to 225 and 135 to obtain

225=135×1+90

Repeat the above step until you will get remainder as zero.

Step 3: Now consider the divisor 135 and the remainder 90, and apply the division lemma to get

135=90×1+45

90=2×45+0

Since the remainder is zero, we cannot proceed further.

Step 4: Hence, the divisor at the last process is 45

So, the H.C.F. of 135 and 225 is 45.

Thank you