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.
Smallest $k$ s.t. $7x+1=9y+2=11z+3=k$, all positive integers
-
1You want the [Chinese Remainder Theorem](http://en.wikipedia.org/wiki/Chinese_remainder_theorem). – 2012-03-10
-
0Personally, 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. – 2012-03-10
-
0I found an argument that’s still pretty advanced for kids under 10 but is a lot more elementary than the CRT. – 2012-03-10
3 Answers
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.
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.
-
0Fascinating method. I either missed this entirely or forgot about it. (I would give my highest vote for this answer) – 2012-03-10
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$.
-
0Cool. I need to be more genius to do maths in this way. Thank you very much. – 2012-03-10
-
0@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. – 2012-03-10
-
0@Bill: But not by Grade IV students, for whom the question was apparently intended: see Gaurav’s comment under the original question. – 2012-03-10
-
0@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$). – 2012-03-10
-
0@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. – 2012-03-10
-
0@Brian By OP I mean "Original Problem", i.e. the original question, which says nothing about grade level. In any case, as I said, I have many times successfully taught easy forms of CRT to bright 10 years olds. Anyone who can understand such an ad-hoc solution can also understand an easy form of CRT with only slightly more effort (presuming a talented teacher). Indeed, if JDH can [teach ordinal arithmetic](http://math.stackexchange.com/a/49046/242) (parity) to younger students, then CRT is a piece of cake! – 2012-03-10
-
0@Bill: And I meant ‘Original Poster’. My answer was very specifically a response to Gaurav’s additional comment, and the ease or otherwise of teaching your pet form of the CRT is irrelevant to the State Board context. (I’m well aware that what is done often differs from what can be done: I’ve taught a bit more ordinal arithmetic than that to possibly more unlikely students. That’s not at issue.) – 2012-03-10
-
0@Brian The ordinal remark was a joke! (see my comments there). But, seriously, this "PET CRT" goes over quite well with students - try it some time. – 2012-03-10