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?

  • 5
    Chinese remainder theorem ?2011-10-18
  • 0
    A concrete algorithm is sketched [here](http://en.wikipedia.org/wiki/Chinese_remainder_theorem#A_constructive_algorithm_to_find_the_solution).2011-10-18
  • 0
    He asked for a clue, not the solution!2011-10-18
  • 4
    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.2011-10-18
  • 0
    thnks for replying..@Andre Nicolas can u tell more about the fancier stuff...2011-10-18
  • 1
    A *general* approach has already been referenced by @Henning Makholm.2011-10-18
  • 1
    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 ... .2011-10-18
  • 0
    **Note** $\ $ See also [this question](http://math.stackexchange.com/q/305482/23500) which gives the same incorrect solution, and which cites the textbook source, which shows an incorrect solution method.2013-02-16
  • 2
    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.2013-02-16

4 Answers 4

9

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.

  • 1
    **BHITW** (Best Hints in the West) :)2011-10-18
  • 0
    @bill had a doubt in the above hint...how is n=9.13??2011-10-18
  • 0
    @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$.2011-10-18
  • 0
    @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\:.$2011-10-18
  • 0
    so from this we get x=8.9.13 which is 936.....but the answer is 881...can u plz xplain a bit further how 2 reach this soln..2011-10-18
  • 0
    @Jay Easy CRT implies the answer is $\rm\ x\equiv 8 + 9\cdot 13\ (-3)\pmod{9\cdot 11\cdot 13}\:.$2011-10-18
  • 0
    mod 11: a−b/n = 9−8/9⋅13 ≡ 1/−2⋅2 ≡ 12/−4 ≡ −3 can anyone xplain this.....?how is 1/-2.2 equivalent to 12/-42011-10-18
  • 0
    @Jay $\rm\ mod\ 11\!:\ 9\equiv -2,\ 13\equiv 2,\ 1 \equiv 12\:,\:$ since $\rm a\equiv b\:$ means $\rm\:11\:|\:a-b\:,\:$ i.e. $\:11\:$ divides $\rm\:a-b\:.\qquad$2011-10-18
  • 0
    How did you get $-2\cdot2$ in your answer?2016-11-27
  • 1
    @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.](http://math.stackexchange.com/a/879262/242)2016-11-27
  • 0
    I see, thanks $\ $2016-11-27
2

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.

2

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.

0

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.