Question

use Euclid's algorithm to find the HCF of 900 and 270
​

Answer 1

Answer:

According to Euclid’s division algorithm, for any integer a and any positive integer b, there exists unique integers q and r such that a=bq+r ( where r is greater than or equal to 0 and less than b or 0⩽r<b). We say that ais the dividend, b is the divisor, q is the quotient and r is the remainder.

Now, we are required to find the highest common factor or H.C.F. of 900 and 270

Let’s start by dividing the larger number by the smaller one and hence, applying the division algorithm.

Hence, we can write the larger number as:

900=270×3+90

We can see that this is in the form of a=bq+r (where r is greater than or equal to 0 and less than b or 0⩽r<b).

Now, we will divide the divisor by the remainder, or 270 by 90

Hence, we get:

270=90×3+0

Now, the remainder has become 0.

Now, according to the division algorithm, the step where the remainder becomes 0 and the procedure stops, the divisor of that step is the required HCF of the given two numbers.

In this case, the divisor in the last step is 90.

Hence, the Highest common factor or HCF of 900 and 270 is 90.

Therefore, this is the required answer.

Note:

Highest common factor or H.C.F. of two numbers is the largest number that divides both the numbers; or in other words, it is the greatest common divisor. Euclid’s Division Algorithm helps us to find the H.C.F. quickly. The difference between a lemma and an algorithm is that a proven statement, which is used for proving other statements, is called a lemma whereas a series of steps used for proving or solving a question is called an algorithm.

_____________________________________

900 and 270 , start with the larger

integer , that is 900. Apply the  

Division lemma , we get

900=270×3+90

270=90×3+0

The remainder has now become  

zero . Now our procedure stops.

Since the divisor at this stage is 90.

Therefore ,

HCF(900,270)=90