Problem Solving

In the first 1000 positive integers, how many integers exist such that they leave a remainder 4 when divided by 7, and a remainder 9 when divided by 11?

A. 10
B. 11
C. 12
D. 13
E. 14

[spoiler]OA: D[/spoiler]

What is the best short cut to this problem?

A quick lesson on remainders:

When x is divided by 5, the remainder is 3.
In other words, x is 3 more than a multiple of 5:
x = 5a + 3.

When x is divided by 7, the remainder is 4.
In other words, x is 4 more than a multiple of 7:
x = 7b + 4.

Combined, the statements above imply that when x is divided by 35 -- the LOWEST COMMON MULTIPLE OF 5 AND 7 -- there will be a constant remainder R.
Put another way, x is R more than a multiple of 35:
x = 35c + R.

To determine the value of R:
Make a list of values that satisfy the first statement:
When x is divided by 5, the remainder is 3.
x = 5a + 3 = 3, 8, 13, 18...
Make a list of values that satisfy the second statement:
When x is divided by 7, the remainder is 4.
x = 7b + 4 = 4, 11, 18...
The value of R is the SMALLEST VALUE COMMON TO BOTH LISTS:
R = 18.

Putting it all together:
x = 35c + 18.

Another example:
When x is divided by 3, the remainder is 1.
x = 3a + 1 = 1, 4, 7, 10, 13...
When x is divided by 11, the remainder is 2.
x = 11b + 2 = 2, 13...

Thus, when x is divided by 33 -- the LCM of 3 and 11 -- the remainder will be 13 (the smallest value common to both lists).
x = 33c + 13 = 13, 46, 79...

Onto the problem at hand:

Mo2men wrote:In the first 1000 positive integers, how many integers exist such that they leave a remainder 4 when divided by 7, and a remainder 9 when divided by 11?

A. 10
B. 11
C. 12
D. 13
E. 14

When x is divided by 7, the remainder is 4.
x = 7a + 4 = 4, 11, 18, 25, 32, 39, 46, 53...
When x is divided by 11, the remainder is 9.
x = 11b + 9 = 9, 20, 31, 42, 53...

Thus, when x is divided by 77 -- the LCM of 7 and 11 -- the remainder will be 53 (the smallest value common to both lists).
x = 77c + 53 = 53, 130, 207...

In the resulting list, the smallest value is yielded when c=0:
77*0 + 53 = 53.
The greatest value less than 1001 is yielded when c=12:
77*12 + 53 = 977.
Implication:
c can be any integer between 0 and 12, inclusive, yielding a total of 13 options.

The correct answer is D.

In a pinch, another approach is to find two numbers that behave like this, then see what they have in common and generalize from there.

If x leaves a remainder of 4 when divided by 7, we can say

x = 7m + 4

where m is some integer whose value we don't care about.

Similarly, if x leaves a remainder of 9 when divided by 11, we can say

x = 11n + 9

where n is some integer whose value we don't care about.

Since x = x, we also have 7m + 4 = 11n + 9, or 7m = 11n + 5. This suggests that we're looking for a multiple of 7 that is 5 greater than a multiple of 11.

Checking the multiples of 11, plus 5, we find

16, 27, 38, 49, 60, 71, 82, 93, 104, 115, 126, ...

Having found two of these, we can generalize that each solution is likely to be (126 - 49) units apart, or 77 units apart. (That should make sense, since 77 = 7*11).

That means that our initial solutions will all be of the form 77*(some integer) + 49, meaning that we have

77*0 + 49
77*1 + 49
77*2 + 49
...

and so on, with our ceiling coming at 1000. 77*13 = 1001, so that's too big, meaning we must only go to 77*12 + 49.

Since we started at 77*0 and made it to 77*12, we have 0 to 12, or 13 solutions, and we're set. To find the actual answers, add 4 to each, since we began by subtracting 4 to simplify. (In other words, our solution set becomes 49+4, 126+4, etc.)

This seems like a little more remainder theory than the GMAT expects of you, however.

Mo2men wrote:In the first 1000 positive integers, how many integers exist such that they leave a remainder 4 when divided by 7, and a remainder 9 when divided by 11?

A. 10
B. 11
C. 12
D. 13
E. 14

[spoiler]OA: D[/spoiler]

What is the best short cut to this problem?

remainder 4 when divided by 7 - Numbers can be 4, 11, 18, 25, 32, 39, 46, 53, ...
remainder 9 when divided by 11 - Numbers can be 9,20, 31, 42, 53, ...

Common numbers less than 1000 will be 53, 77*1 + 53, 77*2 + 53, ...., 77*12 + 53
Hence a total of 13 numbers.

Correct Option: D