2
$\begingroup$

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.

  • 0
    I 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 3

0

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.

3

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.

  • 0
    Fascinating method. I either missed this entirely or forgot about it. (I would give my highest vote for this answer)2012-03-10
1

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$.

  • 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