Question

Use Euclid’s algorithm to find the HCF of 900 and 270.

Answer 1

Hint: Here, we use the algorithm by taking the larger number first and then the smaller number and simplify it further. The divisor of the step where the remainder will become 0 will be the required HCF of the given numbers.

Complete step-by-step 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 \leqslant r < b$). We say that $a$is 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 \times 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 \leqslant r < b$).
Now, we will divide the divisor by the remainder, or 270 by 90
Hence, we get:
$270 = 90 \times 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.