Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
5  
Chinese remainder theorem ? –  The Chaz 2.0 Oct 18 '11 at 2:28
    
A concrete algorithm is sketched here. –  Henning Makholm Oct 18 '11 at 2:30
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. –  André Nicolas Oct 18 '11 at 2:41
1  
A general approach has already been referenced by @Henning Makholm. –  André Nicolas Oct 18 '11 at 3:17
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 ... . –  Matt E Oct 18 '11 at 8:07

3 Answers 3

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 by the special constant case $\rm\,a = b\,$ of Easy CRT (see below). This reduces 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\ 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}{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.

share|improve this answer
1  
BHITW (Best Hints in the West) :) –  The Chaz 2.0 Oct 18 '11 at 3:26
    
@bill had a doubt in the above hint...how is n=9.13?? –  Jay Oct 18 '11 at 3:43
    
@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$. –  Gerry Myerson Oct 18 '11 at 4:07
    
@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\:.$ –  Bill Dubuque Oct 18 '11 at 4:22
    
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.. –  Jay Oct 18 '11 at 4:22

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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