# Smallest $k$ s.t. $7x+1=9y+2=11z+3=k$, all positive integers

Find the smallest positive integer, which on dividing with 7 gives remainder 1, on dividing with 9 gives (remainder) 2 and that after division by 11 yields 3 as remainder. i.e., find smallest $k \in \mathbb{Z}^+$ such that $$k=7x+1=9y+2=11z+3 \ x,y,z \in \mathbb{Z}^+$$. The answer is 344 which I got by observing each number. First of all I wrote all the positive integers which on division with 11 yield 3 as remainder (e.g., 14,25,...) and then tested, whether or not the number after division by 7 and 9 produces the required result. It is a wrong approach to solve such a problem, but I don't know how to solve it theoretically. Thanks for the help.

-
You want the Chinese Remainder Theorem. – Brian M. Scott Mar 10 '12 at 13:43
Personally, I would like to tell that this question was taken from a Grade IV book of an Indian State Board. I don't think Chinese Remainder Therorem could be taught at this level (<10 yrs). BTW thanks. I need to learn this theorem first of all then I'll be able to say anything more. – gaurav Mar 10 '12 at 13:54
I found an argument that’s still pretty advanced for kids under 10 but is a lot more elementary than the CRT. – Brian M. Scott Mar 10 '12 at 14:13

Here’s a solution that doesn’t rely on the Chinese Remainder Theorem and uses only pretty basic knowledge, though it’s still a bit of a stretch for kids under ten.

If $9y+2=11z+3$, then $9y=11z+1$, so we need a multiple of $9$ that is one more than a multiple of $11$. A little quick mental arithmetic finds $45$, one more than $44$; that would make $y=5$ and $z=4$, and of course $k$ would be $47$. Unfortunately, this leaves a remainder of $5$ when divided by $7$.

Note, though, that any number of the form $47+99n$ leaves remainders of $2$ and $3$ when divided by $9$ and $11$, respectively; this is because $99n$ is divisible by both $9$ and $11$. Moreover, $99=7\cdot14+1$, so every time I add $99$, I increase the remainder on division by $7$ by one. I want a remainder of $1$, and $k=47$ gives me a remainder of $5$. Thus, I need to increase the remainder by $3$ (to $6$, then $0$, then $1$), so I add $99$ three times to get $k=47+3\cdot 99=344$.

-
Cool. I need to be more genius to do maths in this way. Thank you very much. – gaurav Mar 10 '12 at 14:50
@guarev No you don't need to be a genius! No ad-hoc tricks are needed here since the answer can be computed algorithmically (and more simply) by using a convenient form of the Chinese Remainder Theorem (CRT) - see my answer. – Bill Dubuque Mar 10 '12 at 17:18
@Bill: But not by Grade IV students, for whom the question was apparently intended: see Gaurav’s comment under the original question. – Brian M. Scott Mar 10 '12 at 17:21
@Brian The OP said nothing about grade-level. However, I have taught CRT to students younger than 10. If one can understand the statement of the problem then one can understand (easy forms) of CRT, especially here where all the inverses are trivial (divisors of modulus $\pm 1$). – Bill Dubuque Mar 10 '12 at 17:27
@Bill: The OP most certainly did, exactly where I directed you to look. I quote: ‘Personally, I would like to tell that this question was taken from a Grade IV book of an Indian State Board. I don't think Chinese Remainder Therorem could be taught at this level (<10 yrs).’ Thus, what one can teach is not at issue; I was trying to see how close I could come to an answer that might be within reach of what is taught. – Brian M. Scott Mar 10 '12 at 17:36

First I present an easy CRT-based high-school-level solution. Then, addressing your above comment, I show a way to present it to grade-school students (which has worked well for me).

The solution is straightforward application of Easy CRT (below). It is so simple that one can do all of the arithmetic mentally. Indeed, applying the general Easy CRT formula we have

$$\rm \begin{eqnarray}\rm x&\equiv&\rm 2\ (mod\ 9) \\ \rm x&\equiv&\rm 3\ (mod\ 11)\end{eqnarray}\!\!\! \iff\!\! x \equiv 3 + 11\: \bigg[\!\!\frac{2\!-\!3}{11} mod\ 9\bigg]\! \equiv 47\ (mod\ 99)\ \ by\ \frac{-1}{11}\equiv \frac{8}{2}\equiv 4 \ (mod\ 9)$$

$$\rm \begin{eqnarray}\rm x&\equiv&\rm\ 1\ \ (mod\ 7) \\ \rm x&\equiv&\rm 47\ (mod\ 99)\end{eqnarray}\!\!\! \iff\!\! x \equiv 47 + 99\ \bigg[\!\!\frac{1\!-\!47}{99} mod\ 7\bigg]\! \equiv 344\ (mod\ 693)\ \ by\ \frac{-46}{99}\equiv \frac{3}{1}\: (mod\ 7)$$

THEOREM (Easy CRT) $\rm\ \$ If $\rm\ m,\:n\:$ are coprime integers then $\rm\ n^{-1}\$ exists $\rm\ (mod\ m)\ \$ and

$\rm\displaystyle\quad \begin{eqnarray}\rm x&\equiv&\rm\ a\ (mod\ m) \\ \rm x&\equiv&\rm\ b\ (mod\ n)\end{eqnarray}\!\!\! \iff\! x\: \equiv\: b + n\ \bigg[\frac{a\!-\!b}{n}\ mod\ m\:\bigg]\ \ (mod\ m\:\!n)$

Proof $\rm\ (\Leftarrow)\quad mod\:\ n\!:\:\ x\:\equiv\: b + n\ (\cdots)\equiv b\:,\$ and $\rm\ mod\ m\!:\ x\equiv b + (a-b)\ n/n\: \equiv\: a\:.$

$\rm\ (\Rightarrow)\ \$ The solution is unique $\rm\ (mod\ m\:\!n)\$ since if $\rm\ x',x\$ are solutions then $\rm\ x'\equiv x\$ mod $\rm\:m,n\:$ therefore $\rm\ m,n\ |\ x'-x\ \Rightarrow\ m\:\!n\ |\ x'-x\ \$ since $\rm\ \:m,n\:$ coprime $\rm\:\Rightarrow\ lcm(m,n) = m\:\!n\ \ \$ QED

Easy CRT is more elementary without the modular inverses. Again, assuming $\rm\:m,n\:$ coprime:

Baby CRT $\rm\displaystyle\quad \begin{eqnarray}\rm x\: \equiv\: a\ &\rm(mod\ m) \\ \rm x\: \equiv\: b\ &\rm(mod\ n)\end{eqnarray} \iff\$ $\begin{eqnarray}\rm a\: &\equiv&\:\rm b + n\:\!y\ &\rm(mod\ m)\\ \rm x \:&\equiv&\:\rm b + n\:\!y\ &\rm (mod\ m\:\!n)\end{eqnarray}\rm\ \ for\ some\:\ y$

For example, let's do the first case above We must first solve solve $\rm\: n\:\!y \equiv a-b\:\ (mod\ m),\:$ i.e. $\rm\:mod\ 9\!:\ 11\:y \equiv - 1\:$ $\Rightarrow$ $\rm\: 2\:y \equiv 8\:$ $\Rightarrow$ $\rm\:y\equiv 4,\:$ thus $\rm\: x\equiv n\:\!y+b\equiv 11\cdot 4+ 3\equiv 47\:\ (mod\ 9\cdot 11).\:$ Of course one may further eliminate the "mod" language by using remainders, if need be.

This approach is usually works well since such problems are usually explicitly constructed to make the arithmetic easy, e.g. as above the inverses (or equivalent linear equations) are trivial to compute (or solve), being divisors of modulus $\pm 1$.

Note $\$ The solution in Brian's answer can be viewed as an application of Baby CRT. He chooses $\rm\:m,n = 11,9\:$ (vs. $9,11$ above). Then he solves by brute-force search $\rm\:mod\ m\!: \rm\: n\:\!y\equiv a-b,\:$ i.e. $\rm\:mod\ 11\!:\ 9\:y\equiv 1.\:\!$ Quicker than searching is to reduce the divisor to least magnitude $\rm\: 9\equiv -2,\:$ to simplify division. This results in the simpler $\rm\:-2\:y \equiv 1\equiv 12\:$ $\Rightarrow$ $\rm\:y\equiv -6\equiv 5.\:$ The second case involves solving $\rm\: mod\ 7\!:\ 99\:\!y\equiv -46\:$ $\Rightarrow$ $\rm\:y\equiv 3,\:$ since $\: 99\equiv 22\equiv 1,\:$ and $\rm {-}46\equiv 49-46\equiv 3.\ \$ These are precisely the same equations that arise when employing Baby CRT, in order $11,9,7$.

So the difference between the two answers amounts to the different approach to solving the linear equations that arise in Baby CRT. I use modular reduction to simplify the equation so that little or no search is needed (exploiting the "law of small numbers"), whereas Brian uses other heuristics.

-
Fascinating method. I either missed this entirely or forgot about it. (I would give my highest vote for this answer) – Kirthi Raman Mar 10 '12 at 18:56

This is solved using the Chinese remainder theorem :-

Take the sum like this:

$$k= 1(\bmod 7) = 2(\bmod 9) = 3(\bmod 11)$$

Check wikipedia and this video tutorial.

-