Question

Use Euclid division algorithm, prove that 847, 2160 are co-prime relatively prime.

Answer 1

Hint: To check if 847 and 2160 are co-prime then we see if the HCF of 847 and 2160 is 1, this is what definition of co-prime is. Then, we will use the Euclid division algorithm which is an algorithm to compute HCF of two numbers. The Euclid division algorithm is followed at the point till the remainder, by dividing both numbers by 1.

Complete step by step answer:
Let us first define what co-primes or relatively prime are. Two numbers a and b are called coprime or relatively prime if they have only one common factor as 1.
Let us assume a = 2160 and b = 847
Now, let us define the Euclid division algorithm.
Euclid division algorithm is a technique to compute the highest common factor (HCF) of two given positive integers.
HCF of two positive integers a and b is the largest positive integer d that divides a and b.
In Euclid division algorithm we consider two positive integer a and b and write it in terms of $a=bq+r$ where $0\le r\le b$ then use ‘b’ in place of a and again use $b=rq'+r'$ where $0\text{ }<\text{ }r'\text{ }<\text{ }r$ this process is repeated unless and until we obtain 0 at place of ‘r’, then r at place above the last line is HCF of two numbers.
Now, let b = 847 and a = 2160 and follow above stated process, we get:
\[2160=847\times 2+466\]
This is obtained as
\[\begin{align}
  & 847\times 2=1694 \\
 & \text{and }2160-1694=466 \\
\end{align}\]
So, r = 466
Again using 847 in place of 2160 and writing as a multiple of 466, we get:
\[847=466\times 1+381\]
Again following the above stated process, we get:
\[\begin{align}
  & 466=381\times 1+85 \\
 & 381=85\times 4+41 \\
 & 85=41\times 2+3 \\
 & 41=3\times 13+2 \\
 & 3=2\times 1+1 \\
 & 2=1\times 2+0 \\
\end{align}\]
So, 0 is obtained at place of r.
Hence, number '1' is HCF of 2160 and 847.
Therefore, 1 is HCF of 2160 and 847.

Thus, the number 2160 and 847 are co-prime.

Note: In the definition of Euclid division algorithm, we have stated two positive numbers a and b. Here, in our question, we had a = 2160 and b = 847, both positive. So, they worked well. But, even if one of them is a negative integer then also, we can calculate the HCF of a number.
Consider 2 and 4 as examples. Then, HCF (2, 4) = 2 and that of -2, 4 is also 2 as HCF is the highest common factor, so, even if we obtain factors as -2 or 2 we will choose highest of 2 and -2 which is 2 not -2.