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.
 A: 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\ \ \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,\:$ so $\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.\:$ In the second case we solve $\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. See here for most all known ways to solve linear congruences like those above.
A: 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$.
A: 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.
