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