• Magoosh
Study with Magoosh GMAT prep

Available with Beat the GMAT members only code

• Get 300+ Practice Questions

Available with Beat the GMAT members only code

• Award-winning private GMAT tutoring
Register now and save up to $200 Available with Beat the GMAT members only code • 1 Hour Free BEAT THE GMAT EXCLUSIVE Available with Beat the GMAT members only code • Free Practice Test & Review How would you score if you took the GMAT Available with Beat the GMAT members only code • Free Veritas GMAT Class Experience Lesson 1 Live Free Available with Beat the GMAT members only code • FREE GMAT Exam Know how you'd score today for$0

Available with Beat the GMAT members only code

• Free Trial & Practice Exam
BEAT THE GMAT EXCLUSIVE

Available with Beat the GMAT members only code

• 5 Day FREE Trial
Study Smarter, Not Harder

Available with Beat the GMAT members only code

• 5-Day Free Trial
5-day free, full-access trial TTP Quant

Available with Beat the GMAT members only code

# This topic has 3 expert replies and 1 member reply

### Top Member

Mo2men Legendary Member
Joined
25 Sep 2015
Posted:
600 messages
Followed by:
5 members
14

#### Tough Reminder Question

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

OA: D

What is the best short cut to this problem?

### GMAT/MBA Expert

GMATGuruNY GMAT Instructor
Joined
25 May 2010
Posted:
14640 messages
Followed by:
1845 members
13060
GMAT Score:
790
Sun Jun 12, 2016 11:38 am
A quick lesson on remainders:

Quote:
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.

_________________
Mitch Hunt
Private Tutor for the GMAT and GRE
GMATGuruNY@gmail.com

If you find one of my posts helpful, please take a moment to click on the "UPVOTE" icon.

Available for tutoring in NYC and long-distance.
Student Review #1
Student Review #2
Student Review #3

Free GMAT Practice Test How can you improve your test score if you don't know your baseline score? Take a free online practice exam. Get started on achieving your dream score today! Sign up now.

### GMAT/MBA Expert

Matt@VeritasPrep GMAT Instructor
Joined
12 Sep 2012
Posted:
2637 messages
Followed by:
114 members
625
Target GMAT Score:
V51
GMAT Score:
780
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.

Enroll in a Veritas Prep GMAT class completely for FREE. Wondering if a GMAT course is right for you? Attend the first class session of an actual GMAT course, either in-person or live online, and see for yourself why so many students choose to work with Veritas Prep. Find a class now!
OptimusPrep Master | Next Rank: 500 Posts
Joined
13 Mar 2015
Posted:
410 messages
Followed by:
7 members
120
GMAT Score:
770
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

OA: D

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

### GMAT/MBA Expert

Scott@TargetTestPrep GMAT Instructor
Joined
25 Apr 2015
Posted:
1349 messages
Followed by:
11 members
43
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.

_________________
Scott Woodbury-Stewart Founder and CEO

### Top First Responders*

1 Jay@ManhattanReview 76 first replies
2 GMATGuruNY 61 first replies
3 Brent@GMATPrepNow 46 first replies
4 Rich.C@EMPOWERgma... 33 first replies
5 ceilidh.erickson 18 first replies
* Only counts replies to topics started in last 30 days
See More Top Beat The GMAT Members

### Most Active Experts

1 Brent@GMATPrepNow

GMAT Prep Now Teacher

107 posts
2 GMATGuruNY

The Princeton Review Teacher

94 posts
3 Jeff@TargetTestPrep

Target Test Prep

93 posts
4 Max@Math Revolution

Math Revolution

91 posts
5 Jay@ManhattanReview

Manhattan Review

88 posts
See More Top Beat The GMAT Experts