Question

Find the greatest number which can divide 257 and 329 so as to leave a remainder 5 in each case.

Answer 1

Hint: We assume the greatest number to be $d$. We denote the quotient as ${{q}_{1}}$ when we divide 257 by the $d$ and denote the quotient as ${{q}_{2}}$ when we divide 329 by $d$. We get a reminder for both numbers $r=5$. We use Euclid’s lemma $n=dq+r$ for both division to find $d$ is greatest common divisor of $257-r,329-r$.

Complete step-by-step solution
We know that in the arithmetic operation of division the number we are going to divide is called the dividend, the number by which divides the dividend is called the divisor. We get a quotient which is the number of times the divisor is of dividend and also remainder obtained at the end of the division. If the number is $n$, the divisor is $d$, the quotient is $q$ and the remainder is $r$, they are related by the following equation,
\[n=dq+r\]
Here the divisor can never be zero. If $r=0$ then $d,q$ are factors of $n$. The above relation is called Euclid’s Division Lemma.
We are asked to find the greatest number which can divide 257 and 329 so as to leave a remainder 5 in each case. Let that greatest divisor be $d$. According to the question when we divide 257 by $d$ it will leave remainder 5. We use Euclid’s lemma for some quotient ${{q}_{1}}$ and remainder $r=5$we have,
\[\begin{align}
  & \Rightarrow 257=d{{q}_{1}}+5 \\
 & \Rightarrow 257-5=d{{q}_{1}} \\
 & \Rightarrow 252=d{{q}_{1}} \\
\end{align}\]
 So $d$ is a factor of 252 .According to the question, when we divide 2329 by $d$ it will leave the remainder 5. We use Euclid’s lemma for some quotient ${{q}_{2}}$ and remainder $r=5$we have,
\[\begin{align}
  & \Rightarrow 329=d{{q}_{1}}+5 \\
 & \Rightarrow 329-5=d{{q}_{1}} \\
 & \Rightarrow 324=d{{q}_{1}} \\
\end{align}\]
So $d$ is a factor of 324. So $d$ is a common factor of both 252 and 324. It is also the greatest common factor otherwise known as GCD which we find from prime factorization of 252 and 324.
\[\begin{align}
  & 252=2\times 2\times 3\times 3\times 7 \\
 & 324=2\times 2\times 3\times 3\times 3\times 3\times 3 \\
 & \text{GCD}=2\times 2\times 3\times 3=36 \\
 & \therefore d=\text{GCD}=36 \\
\end{align}\]

Note: The greatest common divisor (GCD) is also known as the highest common factor (HCF). We can also find GCD in the tabular method. We must be careful of confusion between GCD and LCM where we find the least common multiple. We can put $r=5,n=36$ to find the quotients ${{q}_{1}}=7,{{q}_{2}}=27$.