Tough Reminder Question

Expert replies

Mo2men: Legendary Member; Posts: 712; Joined: Fri Sep 25, 2015 4:39 amFollowed by: 5 members; Thanked: 14 times

by Mo2men » Sun Jun 12, 2016 11:06 am

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?

Like this post

Source: Beat The GMAT — Problem Solving | Sun Jun 12, 2016 11:06 am

GMATGuruNY: GMAT Instructor; Posts: 15539; Joined: Tue May 25, 2010 12:04 pmFollowed by: 1906 members; Location: New York, NY; Thanked: 13060 times; GMAT Score:790

by GMATGuruNY » Sun Jun 12, 2016 11:38 am

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.

Private tutor exclusively for the GMAT and GRE, with over 20 years of experience.
Followed here and elsewhere by over 1900 test-takers.
I have worked with students based in the US, Australia, Taiwan, China, Tajikistan, Kuwait, Saudi Arabia -- a long list of countries.
My students have been admitted to HBS, CBS, Tuck, Yale, Stern, Fuqua -- a long list of top programs.

As a tutor, I don't simply teach you how I would approach problems.
I unlock the best way for YOU to solve problems.

For more information, please email me (Mitch Hunt) at [email protected].
Student Review #1
Student Review #2
Student Review #3

Like this post

Matt@VeritasPrep: GMAT Instructor; Posts: 2630; Joined: Wed Sep 12, 2012 3:32 pmFollowed by: 119 members; Location: East Bay all the way; Thanked: 625 times; GMAT Score:780

by Matt@VeritasPrep » Thu Jun 23, 2016 5:42 pm

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.

Save $100 on any VP online course!

Like this post

OptimusPrep: Master | Next Rank: 500 Posts; Posts: 410; Joined: Fri Mar 13, 2015 3:36 amFollowed by: 8 members; Location: Worldwide; Thanked: 120 times; GMAT Score:770

by OptimusPrep » Fri Jun 24, 2016 8:03 pm

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

Like this post

GMAT/MBA Expert

Scott@TargetTestPrep: GMAT Instructor; Posts: 8136; Joined: Sat Apr 25, 2015 10:56 amFollowed by: 29 members; Location: Los Angeles, CA; Thanked: 43 times

by Scott@TargetTestPrep » Fri Aug 10, 2018 6:01 pm

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

We need to find the smallest integer that satisfies both conditions:

Numbers that leave a remainder of 4 when divided by 7 are:

4, 11, 18, 25, 32, 39, 46, 53, ...

Numbers that leave a remainder of 9 when divided by 11 are:

20, 31, 42, 53, ...

We see that 53 is the first number that satisfies both conditions. To find the subsequent numbers that also satisfy both conditions we keep adding the LCM of 7 and 11, i.e., 77, to (and beginning with) 53. So the numbers, including 53, are:

53, 130, 207, 284, 361, 438, 515, 592, 669, 746, 823, 900, and 977

So there are a total of 13 such numbers.

Answer: D

Scott Woodbury-Stewart
Founder and CEO
[email protected]

See why Target Test Prep is rated 5 out of 5 stars on BEAT the GMAT. Read our reviews

Like this post

Post new topic Post Reply

• Page 1 of 1

GMAT Course Reviews

559 reviews

1168 reviews

431 reviews

359 reviews

147 reviews

5/5

5 Star (560 Reviews)

"Target Test Prep is the closest to the official version of the GMAT exam, about 99% accuracy in terms of the quality and quantity of information. The course has excellently created singular sets of focused lessons and tests for every possible topic that one could come across in the official GMAT exam."

"The TTP course maximizes the efficiency of the time you spend studying. It will take time and effort but I could almost guarantee that if you complete the course exactly as it is laid out you will get an amazing score. They also have a very responsive team willing to help with any questions you might have."

"TTP has two things that I think no other test prep company offers: A teaching approach that reinforces understanding and an attitude that will give you the mental preparedness needed to succeed on the test. TTP gives you a deep understanding of the concept you need to know while teaching you how to think."

Write a Review