Question

To find the HCF by using Euclid’s algorithm of
A. $$135$$ and$$225$$
B. $$196$$ and $$38220$$
C. $$867$$ and $$255$$
D. Show that any positive odd integer is of the form $$6q+1$$, or $$6q+3$$, or $$6q+5$$ where q is some integer.

Answer 1

Hint: Here the objective is to find the HCF by using Euclid’s division algorithm. First we have to find the HCF of given integers by using Euclid’s Division Lemma. It is a method to compute the highest common factor of two given positive integers. Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.

Complete step-by-step solution:
(i) By Euclid’s division lemma we know that $$a=bq+r,0⩽r<b$$.
Here $$225$$ is greater than $$135$$.
Therefore, $$225=135\times 1+90$$.
Here the remainder $$90\ne 0$$, thus again repeating the lemma for $$90$$,
$$135=90\times 1+45$$
Here, the remainder $$45\ne 0$$, thus again repeating the lemma for $$45$$,
$$90=45\times 2+0$$
Here, the remainder is $$0$$.
Since the divisor is $$45$$, hence, $$HCF\left(225,135\right)=HCF\left(135,90\right)=HCF\left(90,45\right)=45$$
Hence, the HCF of $$225$$ and $$135$$is $$45$$.

(ii) By Euclid’s division lemma we know that $$a=bq+r,0⩽r<b$$.
Here $$38220$$ is greater than $$196$$.
Therefore, $$38220=196\times 195+0$$.
Here, the remainder is $$0$$.
Hence, $$HCF\left(196,38220\right)=196$$
Hence, the HCF of $$196$$ and $$38220$$ is $$196$$.
(iii) By Euclid’s division lemma we know that $$a=bq+r,0⩽r<b$$.
Here $$867$$ is greater than $$225$$.
Therefore, $$867=225\times 3+102$$.
Here the remainder $$102\ne 0$$, thus again repeating the lemma for $$120$$,
$$225=102\times 2+51$$
Here, the remainder $$51\ne 0$$, thus again repeating the lemma for $$51$$,
$$102=51\times 2+0$$
Here, the remainder is $$0$$.
Since the divisor is $$51$$, hence, $$HCF\left(867,225\right)=HCF\left(225,102\right)=HCF\left(102,51\right)=51$$
Hence, the HCF of $$867$$ and $$225$$ is $$51$$.
(iv) Suppose there is a positive integer ‘a’. Now we have to prove that ‘a’ is of the form $$6q+1$$, or $$6q+3$$, or $$6q+5$$ where q is some integer.
Since ‘a’ is any positive integer, letting b to be 6 as another integer. Now applying Euclid’s division lemma, we get
$$a=6q+r$$ for some integer $$q⩾0$$ and $$r=0,1,2,3,4,5$$ since $$0⩽r<6$$
Now substituting the value of r, we get
If $$r=0$$, then $$a=6q$$
Similarly, substituting the values of $$r=1,2,3,4,5$$, we get the values $$6q+1,6q+2,6q+3,6q+4,6q+5$$respectively.
If $$a=6q,6q+2,6q+4$$, then a is a positive even number which is divisible by 2. A positive integer can be either even or odd. Therefore, any positive odd integer is of the form of $$6q+1,6q+3,6q+5$$, where q is some integer.

Note: Euclid’s division lemma helps to find the highest common factor for the largest integer that leaves a remainder zero for all numbers.
Euclid’s division lemma says that the given two positive integers a and b there exist unique integers q and r such that,
$$a=bq+r,0⩽r<b$$
The integer q is the quotient, and the integer r is the remainder. The quotient and remainder are unique.