Question

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

Answer 1

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 \leqslant r < b$.
Step 2: if $r = 0$, the HCF is $b$. If $r \ne 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 $a$and $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 \times 2 + 176 \\

   \Rightarrow b = 275,q = 2,r = 176 \\

$

Since $r \ne 0$, applying Euclid’s lemma to $b$ and $r$, we get

\[

  275 = 176 \times 1 + 99 \\

   \Rightarrow b = 275,q = 1,r = 99 \\

\]

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

\[

  176 = 99 \times 1 + 77 \\

  99 = 77 \times 1 + 22 \\

  77 = 22 \times 3 + 11 \\

  22 = 11 \times 2 + 0 = bq + r \\

   \Rightarrow 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.

Note: HCF of two prime numbers is equal to one as a prime number has only two factors, one and the number itself. Always apply the division lemma to the largest number of the two while using Euclid’s division algorithm to calculate HCF. HCF of the two numbers will always be less than equal to the smaller of the numbers of which HCF is being calculated.