Question on number system to find integral solutions from the given expressions.

48 Views Asked by At

If the numbers $\frac{k+2}{3}, \frac{k+3}{5}, \frac{k+4}{7}$ are integers which need not be same, then what would be the smallest possible integral $k$ which satisfies the condition.

What would be the simplest way to find the value of $k$. Is there a generalized method to find such values to make the expressions integral. By hit and trial I got $k$ as $52$.

2

There are 2 best solutions below

0
On BEST ANSWER

You can rewrite the system as $$\begin{cases}k\equiv1\pmod3\\k\equiv2\pmod5\\k\equiv3\pmod7\end{cases}$$

Since $3$, $5$ and $7$ are co-prime, the Chinese remainder theorem tells us that there exists a unique solution modulo $3\times5\times7=105.$

From the first congruence we obtain $k=1+3a$ for some $a\in\mathbb Z$, so substituting into the second we obtain $1+3a\equiv2\pmod5$ so $3a\equiv1\pmod5.$ Since $2\times3\equiv1\pmod5$, by multiplying the above congruence by $2$ we have $2\times3a\equiv a\equiv 2\pmod{5},$ so $a=2+5b$ for some $b\in\mathbb Z.$

Now we have $k=1+3a=1+3(2+5b)=7+15b$ and we use the last congruence.

$7+15b\equiv3\pmod7$ so $15b\equiv3\pmod7$ and since $15\equiv1\pmod7$ we obtain that $b\equiv3\pmod7$ and thus $b=3+7c$ for some integer $c$.

Finally we obtain $k=7+15b=7+15(3+7c)=52+105c$, or $k\equiv 52\pmod{105}.$ Thus the smallest positive integer with satisfies the above system of congruences is $52$.

0
On

Although the generalized method uses Chinese Remainder Theorem, the simplest method involves hit and trial.

We are going to find the smallest integer $k$ such that it has a remainder of $1, 2, 3$ when divided by $3, 5, 7$ respectively.

We see that $3$ has a remainder of $3$ when divided by $7$. (duh)

However $3$ does not satisfy the other conditions. To preserve this remainder, we move on to $3+7=10$.

$10$ also has a remainder of $3$ when divided by $7$. Now $10$ has a remainder of $1$ when divided by $3$, but a remainder of $0$ when divided by $5$. To preserve the remainders, we add $3\times 7=21$ to $10$.

We see that $31$ has a remainder of $1$ when divided by $5$, so we keep going.

We arrive at $52$, which satisfies all conditions.


If the numbers involved are not large, this method is usually faster than using the "general method".