4
$\begingroup$

A number when successively divided by $9$, $11$ and $13$ leaves remainders $8$, $9$ and $8$ respectively.

The answer is $881$, but how? Any clue about how this is solved?

$\endgroup$
  • 5
    $\begingroup$ Chinese remainder theorem ? $\endgroup$ – The Chaz 2.0 Oct 18 '11 at 2:28
  • 4
    $\begingroup$ Depends how much machinery you want to use. For little machinery, take advantage of the particular numbers. The remainder on division by $9 \cdot 13=117$ is $8$, so search starting with $8$, then $8+117$, then $8+2\cdot 117$, and so on. Success will come soon. But if you are taking a number theory course, you may be expected to use fancier stuff. $\endgroup$ – André Nicolas Oct 18 '11 at 2:41
  • 1
    $\begingroup$ A general approach has already been referenced by @Henning Makholm. $\endgroup$ – André Nicolas Oct 18 '11 at 3:17
  • 1
    $\begingroup$ If I am not mistaken, $881 = 80\cdot 11 + 1$, and so has a remainder of $1$ upon division by $11$, not a remainder of $9$. I would recheck your solution if I were you ... . $\endgroup$ – Matt E Oct 18 '11 at 8:07
  • 2
    $\begingroup$ The confusion here arises from a misunderstanding about what is meant by "successive" divisions. It is not that one number $N$ has remainders 8,9,8 when divided by 9, 11, 13 (as would be the case with congruences) but that having divided by 9 and obtained a quotient with remainder 8, that quotient is divided by 11 to get remainder 9. CRT solves the "concurrent" problem, not the "successive" one. $\endgroup$ – Mark Bennet Feb 16 '13 at 17:33
10
$\begingroup$

Note $\ $ A newer duplicate question with cited source makes it clear that this is not a CRT problem (as was inferred in the above comments) but, more simply, a question on iterated division with remainder. The answer below is for the CRT interpretation.

Hint $\ $ Note that $\rm\ x\equiv 8\:\ (mod\ 9),\ x\equiv 8\:\ (mod\ 13)$ $\iff$ $\rm x\equiv 8\:\ (mod\ 9\cdot 13),\:$ follows from CCRT = special constant case $\rm\,a\! =\! b\,$ of Easy CRT (below), reducing the $3$ equations to these $2$:

$$\begin{array}{ll}\rm x\ \equiv\ 9\ \ (mod\ \ 11)\\ \rm x\ \equiv\ 8\ \ (mod\ 9\cdot\! 13)\end{array}$$

Applying Easy CRT (below) with $\rm\ a=9,\ b = 8,\ n=\:9\cdot 13,\ m=11,\ $ noting that

$$\rm mod\:\ m\!=\!11\!:\ \ \frac{a-b}{n}\ =\ \frac{9-8}{9\cdot 13}\ \equiv\ \frac{1}{-2\cdot 2}\ \equiv\ \frac{12}{-4}\ \equiv\ {-3}\ \equiv\ \color{#C00}8 $$

we quickly obtain the unique solution: $\rm\ \ x\, \equiv\, 8 + 9\cdot 13\cdot [\color{#C00}8]\,\equiv\, 944 \ \ (mod\,\ 11\cdot9\cdot 13)$

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

$\rm\displaystyle\quad\quad\quad\quad\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}{\color{#0a0}n}\ mod\ m\:\bigg]\ \ (mod\ mn)$

Proof $\rm\ (\Leftarrow)\ \ \ 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\ mn)\ $ since if $\rm\ x',x\ $ are solutions then $\rm\ x'\equiv x\ $ mod $\rm\:m,n\:$ therefore $\rm\ m,n\ |\ x'-x\ \Rightarrow\ mn\ |\ x'-x\ \ $ since $\rm\ \:m,n\:$ coprime $\rm\:\Rightarrow\ lcm(m,n) = mn\:.\ \ $ QED

Note $\ $ The constant case optimization of CRT = Chinese Remainder Theorem frequently proves handy in practice, e.g. see also this answer, where it shortens a few-page proof to a few lines.

$\endgroup$
  • 1
    $\begingroup$ BHITW (Best Hints in the West) :) $\endgroup$ – The Chaz 2.0 Oct 18 '11 at 3:26
  • $\begingroup$ @bill had a doubt in the above hint...how is n=9.13?? $\endgroup$ – Jay Oct 18 '11 at 3:43
  • $\begingroup$ @Jay, Bill noticed that you wanted the same remainder, 8, on division by both 9 and 13, so, since 9 and 13 are relatively prime, that means you want remainder 8 when you divide by $9\times13$. $\endgroup$ – Gerry Myerson Oct 18 '11 at 4:07
  • $\begingroup$ @Jay It's as Gerry says, namely the special constant case $\rm (a = b)$ of Easy CRT, therefore $\rm\ x = b + n\ [(b-b)/n\ mod\ m] = b\ \ (mod\ m\:n)\:\,\ $ for $\rm\: a = b = 8,\ \ m = 9,\ \ n = 13\:.$ More explicitly $\rm\:9,13\:|\:x-8\ \Rightarrow\ 9\cdot 13 = lcm(9,13)\:|\:x-8\:.$ $\endgroup$ – Bill Dubuque Oct 18 '11 at 4:22
  • 1
    $\begingroup$ @suomynonA $\ {\rm mod}\ 11\!:\ \begin{align} \color{#c00}{9\equiv -2}&\\ \color{#0a0}{13\ \equiv\ 2}&\end{align}\Rightarrow\, \color{#c00}{9}\cdot \color{#0a0}{13}\equiv \color{#c00}{-2}\cdot \color{#0a0}{2}\ $ by the Congruence Product Rule. $\endgroup$ – Bill Dubuque Nov 27 '16 at 19:10
2
$\begingroup$

Program your computer to divide the numbers 1, 2, 3, etc., by 9, 11, and 13, and to report to you when it finds the remainders are, respectively, 8, 9, and 8. This approach will teach you more about computer programming than about Number Theory, so it may not be what you want - but it is absolutely for certain a way to solve the problem.

$\endgroup$
2
$\begingroup$

Work backwards. The easiest number that leaves a remainder of $8$ when dividing by $13$ is $8$ itself. Then $8 \cdot 11 + 9 = 97$ will leave a quotient of $8$ and a remainder of $9$ for the division by $11$. Then $9 \cdot 97+8=881$ is what you are looking for.

$\endgroup$
0
$\begingroup$

First when the number is divided by 9. the remainder is 8.

So N = 9x+8.

Similarly, next x = 11y+9, and y=13z+8.

So N = 99y+89 = 99(13z+8)+89 = 1287z+792+89 = 1287z+881.

So N is of the form, 1287*(A whole Number)+881.

If you need to find the minimum number, then it would be 881.

Hope that helps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.