S96-03

Official Solution:

Positive integer \(n\) leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5. If \(n\) is greater than 30, what is the remainder that \(n\) leaves after division by 30?

A. 3
B. 12
C. 18
D. 22
E. 28


The simplest way to approach this problem is to work backwards from the answer choices. Let's construct a possible value of \(n\) for each choice, and then test those values against the given constraints.

Since we are asked for the remainder after division by 30, the easiest possible value of \(n\) for each choice is 30 more than the choice.

(A) \(3 + 30\) gives us \(n = 33\)

(B) \(12 + 30\) gives us \(n = 42\)

(C) \(18 + 30\) gives us \(n = 48\)

(D) \(22 + 30\) gives us \(n = 52\)

(E) \(28 + 30\) gives us \(n = 58\)

Now test those values of \(n\) against the constraints.

(A) \(n = 33\) divided by 6 gives remainder 3 - FAIL

(B) \(n = 42\) divided by 6 gives remainder 0 - FAIL

(C) \(n = 48\) divided by 6 gives remainder 0 - FAIL

(D) \(n = 52\) divided by 6 gives remainder 4 - PASS

(E) \(n = 58\) divided by 6 gives remainder 4 - PASS

We can now just test the surviving choices for how they behave upon division by 5. To leave remainder 3 after division by 5, a number must end in either 3 or 5:

(D) \(n = 52\) divided by 5 gives remainder 2 - FAIL

(E) \(n = 58\) divided by 5 gives remainder 3 - PASS

Another way to approach this problem is to translate the given language of remainders into the language of multiples. If \(n\) leaves a remainder of 4 after division by 6, then \(n\) is 4 more than a multiple of 6. Leaving aside the size requirement for a moment, we can see that \(n\) could be 4, 10, 16, 22, 28, 34, etc.

Likewise, if \(n\) leaves a remainder of 3 after division by 5, then \(n\) is 3 more than a multiple of 5. Again leaving aside the size requirement, we can see that \(n\) could be 3, 8, 13, 18, 23, 28, 33, etc. As we noted earlier, \(n\) must end in 3 or 8.

We might now spot 28 on both lists. Although \(n\) is not actually allowed to be 28 (because \(n\) must be larger than 30), we might try adding 30 to it to get 58. Since 30 is a multiple of 6, adding 30 to 28 won't change the fact that after division by 6, we'll get 4 as the remainder. The same idea holds true for 5: since 30 is a multiple of 5, adding 30 to 28 won't change the fact that after division by 5, we'll get 3 as the remainder. This way, we have constructed a possible \(n\) without using the answer choices.

Finally, the remainder after dividing 58 by 30 is 28.


Answer: E