hard OG remainder & multiple problem

This topic has expert replies
Senior | Next Rank: 100 Posts
Posts: 49
Joined: Thu Jun 30, 2011 2:47 pm
Thanked: 1 times

hard OG remainder & multiple problem

by Redhorsep » Thu Sep 15, 2011 1:11 pm
Hi,

Please help me out with this problem, thanks! It's from OG quant 2nd edition

When positive integer n is divided by 5, the remainder is 1. When n is divided by 7, the remainder is 3. What is the smallest positive integer k such that k+n is a multiple of 35?
Source: — Problem Solving |

User avatar
GMAT Instructor
Posts: 15539
Joined: Tue May 25, 2010 12:04 pm
Location: New York, NY
Thanked: 13060 times
Followed by:1906 members
GMAT Score:790

by GMATGuruNY » Thu Sep 15, 2011 1:30 pm
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

Master | Next Rank: 500 Posts
Posts: 150
Joined: Thu May 05, 2011 10:04 am
Thanked: 5 times
Followed by:4 members

by thestartupguy » Thu Sep 15, 2011 1:38 pm
The number n = 5k+1
Also, n = 7m+3

Therefore, 5k+1=7m+3 or 5k=7m+2.

Now, putting values 1, 2, 3 ,4 and so on. By trial and error we get m = 4 which satisfies the above equation. We take the lowest value.

Therefore n = 31, n + k which is a multiple of 35 will have k = 4.

User avatar
Legendary Member
Posts: 504
Joined: Tue Apr 19, 2011 1:40 pm
Thanked: 114 times
Followed by:11 members

by knight247 » Thu Sep 15, 2011 1:53 pm
For this problem your gonna have to learn to manipulate the form D=qd+R where D=dividend q=quotiend d=divisor and R= remainder

Substituting the info given about n using the above equation we have

n=5a+1 (where a is the quotient)
n=7b+3 (where b is the quotient).......(1)

Equating both sides we get
5a+1=7b+3
7b=5a-2
7b=5c+5-2 (where 5c=5a-5....This another manipulation of the above form that i spoke about)

7b=5c+3

Comparing this with the form D=kd+R we have 7b when divided by 5 gives a quotient of c and remainder of 3. When does a number divided by 5 leave a remainder of 3? As all multiples of 5 end in 5 or 10 the only numbers that will leave a remainder of 3 when divided by 5 are numbers ending in 3 or 8. So 7 b is some multiple of 7 ending in 3 or 8. Lets list them down
7b could be 28,63,98,133,203 etc
aka
7b could be 7(4),7(9),7(19),7(29) etc
So b could be 4,9,19,29 etc

We pick the smallest value from among them and put this in eqn1 we get
n=28+3
n=31
Now some number k needs to be added to n that will make it equal some multiple of 35. The smallest one is 4.



The other way as Mitch has shown. List all the possible numbers which when divided by 5 leave a remainder of 1. eg 1,6,11,16,21,26,31,35 etc

List all the possible numbers which when divided by 7 leave a remainder of 3 3,10,17,24,31,33,40 etc
The smallest number common to both lists is 31 and when 4 is added to it, it becomes a multiple of 35.