3
$\begingroup$

Which is the largest three digit number which when divided by 6 leaves the remainder 5 and when divided by 5 leaves the remainder 3?

What I did:

On division by 6 leaves remainder 5

So numbers are 6, 11, 17, 23

On division by 5 leaves remainder 3

3,8,13,18,23

So common number between the two is 23. Largest three digit number divisible by 23 is 989

But answer is 983. How?

This is a gmat exam question.

$\endgroup$
6
$\begingroup$

You don't want "divisible by $23$." $46$ is divisible by $23$ but it doesn't have the property you want.

You want a number which can be written $30k+23$, where $30=6\cdot 5$.

The general way to do this problem is called the Chinese Remainder Theorem.

$\endgroup$
3
$\begingroup$

If you want to look at the data first, before looking for reasons why it is so, you can list all the values meeting each of your conditions up to some convenient limit:

$\begin{array}{|c|c|} \hline 5\bmod 6 & 3\bmod 5 \\ \hline 5 & 3 \\ 11 & 8 \\ 17 & 13 \\ \color{red}{\fbox{23}} & 18 \\ 29 & \color{red}{\fbox{23}} \\ 35 & 28 \\ 41 & 33 \\ 47 & 38 \\ \color{blue}{\fbox{53}} & 43 \\ 59 & 48 \\ 65 & \color{blue}{\fbox{53}} \\ 71 & 58 \\ 77 & 63 \\ \color{orange}{\fbox{83}}& 68 \\ 89 & 73 \\ & 78 \\ & \color{orange}{\fbox{83}} \\ & 88 \\ \hline \end{array}$

which will give you a much stronger intuition of what to expect of the answer. As you can see the gap between successive answers that match both conditions is $30$, as identified from the theoretical approaches.

$\endgroup$
4
  • $\begingroup$ 53 didn't get highlighted in red in your table. I guess it is blue, but it is hard to see the difference between blue and black in my browser (Chrome) (but easy to see in IE 11 and moderately easy in Edge) $\endgroup$
    – Χpẘ
    Aug 23 '17 at 22:10
  • $\begingroup$ $23$ is red, $53$ is blue, $83$ is orange. If you think blue is hard to see, the default green is worse. :-) Added boxes. $\endgroup$
    – Joffan
    Aug 23 '17 at 22:38
  • $\begingroup$ Thanks for updating. Also handy to see Mathjax for building table. Wow, didn't even notice the color difference between 23 and 83 before, but see it now. Imagine difficulty for folks w color blindness... $\endgroup$
    – Χpẘ
    Aug 23 '17 at 22:45
  • $\begingroup$ A good lesson to learn from this answer: if you don't already have a very good reason to say what the pattern is (why should it be multiples of $23$?), one way to proceed is to work out the first few examples of the property or formula to try to see what the pattern is. $\endgroup$
    – David K
    Aug 24 '17 at 12:29
2
$\begingroup$

You need not a multiple of $23$, but rather $23$ (which sorts out the congruences/residues/remainders) plus a multiple of $5\times 6=30$ (which does not alter them).

You should easily see that $989$ is wrong because it obviously leaves remainder $4$ when divided by $5$.

$\endgroup$
2
$\begingroup$

Hint You figured out that 23 is the smallest such number.

Now, if $n$ is the number you are looking for, show that $n-23$ is divisible by both $5$ and $6$, hence by $30$.

$\endgroup$
2
$\begingroup$

We know one solution $x = 23.\,$ If $x'$ is another solution then $\,x'= 5+6j,\ x= 5+6k\,$ so $\, x'-x = 6(j-k)\,$ is a multiple of $6$. Similarly $\,x'-x\,$ is a multiple of $5$. Thus $\,x'-x\,$ is a multiple of their lcm $= 30.\,$ Conversely if $\,x'-x=30n\,$ then $x',x$ have equal remainders $x$ mod $5$ and $6$.

So the solutions are precisely integers of form $\,23+30n$. The largest multiple of $30$ below $1000$ is clearly $990$ and adding $23$ to that is too big, so we need to subtract $30$ then add $23$, yielding $983$.

$\endgroup$
0
$\begingroup$

We can write this as:

  • 6a+5=5b+3
  • 5b-6a=2
  • 5b(mod 6)≡2(mod 6), thus b≡4(mod 6). We can write b as 6x+4.

Our three digit number is then 5(6x+4)+3=30x+23. 30x+23<=999. The largest integer x that satisfies this is 32. Thus, our three digit number is 30(32)+23=983

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