Question

Find HCF of \[867\] and \[225\], using Euclid’s division algorithm.

Answer 1

Hint: We can find the HCF of a given number using Euclid’s division lemma. According to Euclid’s division lemma if we have two positive integers a and b, then there exist unique integers a and b, then there exist unique integers q and r which satisfies the condition \[a = bq + r\] where \[0 \leqslant r \leqslant b\]

Complete step-by-step answer:
Step 1: \[867\]is greater than \[225\] let us apply Euclid’s division lemma to \[867\] with \[275\] as the divisor we get
\[ \Rightarrow 867 = (225 \times 3) + 192\]
Step 2: since the remainder \[192 \ne 0\]we apply division lemma to \[225\] with \[192\] as the divisor we get
\[ \Rightarrow 225 = (192 \times 1) + 33\]
Step 3: again, the remainder \[33 \ne 0\] we apply division lemma to \[192\] with \[33\] as the divisor we get
\[ \Rightarrow 192 = (33 \times 5) + 27\]
Step 4: the remainder \[27 \ne 0\] we apply division lemma to \[33\] with \[27\]as the divisor we get
\[ \Rightarrow 33 = 27 \times 1 + 6\]
Step 5: the remainder \[6 \ne 0\] we apply division lemma to \[6\] with \[27\]as the divisor we get
\[ \Rightarrow 27 = 6 \times 4 + 3\]
Step 6: the remainder \[3 \ne 0\] we apply division lemma to \[3\] with \[6\] as the divisor we get
\[ \Rightarrow 6 = 3 \times 2 + 0\]
Step 7: the remainder has now become zero.so the divisor at this stage is \[3\].
Therefore, the HCF of\[867\]and \[225\]is \[3\]
So, the correct answer is “3”.

Note: HCF of two given positive integers a and b is the largest positive integer ‘d’ that divides both a and b. The process of finding the HCF of two given positive numbers using Euclid’s division lemma is called Euclid’s division algorithm. The difference between Euclid’s division lemma and Euclid’s division algorithm is that Euclid’s division lemma is a proven statement used for proving another statement while an algorithm is a series of well-defined steps that give a procedure for solving a type of problem.