N is the smallest Number.

Expert replies

goyalsau: Legendary Member; Posts: 866; Joined: Mon Aug 02, 2010 6:46 pm; Location: Gwalior, India; Thanked: 31 times

by goyalsau » Tue Jan 04, 2011 8:47 pm

I am not able to recall the technique by which by which we solve such problems........ Please Help Guys........

if n is the smallest number that leaves respective remainders of 4, 6 and 9 when divided successively by 13, 11 and 15.

Saurabh Goyal
[email protected]
-------------------------

EveryBody Wants to Win But Nobody wants to prepare for Win.

Like this post

Source: Beat The GMAT — Problem Solving | Tue Jan 04, 2011 8:47 pm

shovan85: Community Manager; Posts: 991; Joined: Thu Sep 23, 2010 6:19 amFollowed by: 24 members; Location: Bangalore, India; Thanked: 146 times

by shovan85 » Tue Jan 04, 2011 9:26 pm

goyalsau wrote:I am not able to recall the technique by which by which we solve such problems........ Please Help Guys........

if n is the smallest number that leaves respective remainders of 4, 6 and 9 when divided successively by 13, 11 and 15.

The n can be written as,

n = 13k + 4
n = 11k' + 6
n = 15k" + 9

So, in order to get the number we have to fullfil the above mentioned numbers one by one....

The number with 15 divided 9 as remainder = 15x+9
The number with 11 divided 6 as remainder = 11*(15x+9) + 6
The number with 13 divided 4 as remainder = 13*[11*(15x+9) + 6] +4 = 2145x +1369 (Thus the general form of the required number)

In order to get the lowest put x= 1 thus 3514

If the problem is Easy Respect it, if the problem is tough Attack it

Like this post

Deepthi Subbu: Master | Next Rank: 500 Posts; Posts: 298; Joined: Tue Feb 16, 2010 1:09 amFollowed by: 1 member; Thanked: 2 times

by Deepthi Subbu » Tue Jan 04, 2011 9:43 pm

shovan85 wrote:
goyalsau wrote:I am not able to recall the technique by which by which we solve such problems........ Please Help Guys........

if n is the smallest number that leaves respective remainders of 4, 6 and 9 when divided successively by 13, 11 and 15.
The n can be written as,

n = 13k + 4
n = 11k' + 6
n = 15k" + 9

So, in order to get the number we have to fullfil the above mentioned numbers one by one....

The number with 15 divided 9 as remainder = 15x+9
The number with 11 divided 6 as remainder = 11*(15x+9) + 6
The number with 13 divided 4 as remainder = 13*[11*(15x+9) + 6] +4 = 2145x +1369 (Thus the general form of the required number)

In order to get the lowest put x= 1 thus 3514

Great technique , thanks Shovan.

Like this post

GMAT/MBA Expert

Anurag@Gurome: GMAT Instructor; Posts: 3835; Joined: Fri Apr 02, 2010 10:00 pmFollowed by: 523 members; Location: Milpitas, CA; Thanked: 1854 times; GMAT Score:770

by Anurag@Gurome » Tue Jan 04, 2011 10:21 pm

goyalsau wrote:if n is the smallest number that leaves respective remainders of 4, 6 and 9 when divided successively by 13, 11 and 15.

This is a high level remainder problem.
The solution Shovan provided is not correct. Check the number. It satisfies the 13 criteria only. The following solution contains some critical logical reasoning. Read carefully. If there is any problem, let me know.

The number should be written in the following ways,

1. n = 11a + 6
2. n = 13b + 4
3. n = 15c + 9

Where a, b, and c are non-negative integers.

Our job is to combine all these three to get a single expression for n, from which we can easily determine the smallest possible value.

Combining first two relation we can say (13b + 4) gives a remainder of 6 when divided by 11. Now, (13b + 4) = 11b + (2b + 4). Hence (2b + 4) also gives a remainder of 6 when divided by 11. Which again implies 2b will give a remainder of (6 - 4) = 2 when divided by 11. Hence b will give a remainder of 1 when divided by 11. Thus, b can be written as (11x + 1) for some non-negative integer x.

Hence, n = 13*(11x + 1) + 4 = (143x + 17)

Now we have to combine this with the third relation. Which clearly implies (143x + 17) will give a remainder of 9 when divided by 15. Now, (143x + 17) = (135x + 8x + 15 + 2) = 15*(9x + 1) + (8x + 2). Hence (8x + 2) also gives a remainder of 9 when divided by 15. Which again implies 8x will give a remainder of (9 - 2) = 7 when divided by 15. Thus, 8x must be of the form (15y + 7) for some non-negative integer y. Note that this means 8 divides (15y + 7) = (8y + 7y + 7) = 8y + 7(y + 1). Again this implies 8 divides 7(y + 1). Now as 8 doesn't divide 7, 8 must divide (y + 1). Thus y) must be of the form (8z + 7) for some non-negative integer z. Hence, 8x = (15y + 7) = 15*(8z + 7) + 7 = (120z + 112) = 8*(15z + 14). hence x is of the form (15z + 14) for some non-negative integer z.

Hence, n = 13*(11x + 1) + 4 = (143x + 17) = 143*(15z + 14) + 17 = (2145z + 2019)

Hence minimum possible value of n is 2019.

Note: I believe the original question belongs to CAT and it looks something like "Find the sum of the remainders obtained when a number n is divided by 9 and 7 successively, if n is the smallest number that leaves respective remainders of 4, 6 and 9 when divided successively by 13, 11 and 15."
Am I right Saurabh?

Last edited by Anurag@Gurome on Tue Jan 04, 2011 10:40 pm, edited 1 time in total.

Anurag Mairal, Ph.D., MBA
GMAT Expert, Admissions and Career Guidance
Gurome, Inc.
1-800-566-4043 (USA)

Join Our Facebook Groups
GMAT with Gurome
https://www.facebook.com/groups/272466352793633/
Admissions with Gurome
https://www.facebook.com/groups/461459690536574/
Career Advising with Gurome
https://www.facebook.com/groups/360435787349781/

Like this post

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 » Tue Jan 04, 2011 10:36 pm

goyalsau wrote:I am not able to recall the technique by which by which we solve such problems........ Please Help Guys........

if n is the smallest number that leaves respective remainders of 4, 6 and 9 when divided successively by 13, 11 and 15.

I would simply try the answer choices -- starting with the smallest -- until I found one that satisfies all the conditions given.

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

goyalsau: Legendary Member; Posts: 866; Joined: Mon Aug 02, 2010 6:46 pm; Location: Gwalior, India; Thanked: 31 times

by goyalsau » Tue Jan 04, 2011 10:46 pm

Anurag@Gurome wrote: Note: I believe the original question belongs to CAT and it looks something like "Find the sum of the remainders obtained when a number n is divided by 9 and 7 successively, if n is the smallest number that leaves respective remainders of 4, 6 and 9 when divided successively by 13, 11 and 15."
Am I right Saurabh?

Sir, You are absolutely right,
Problem is from www.time4education.com sectional test under the Heading Number system..
What more can i say on this...

:roll: :roll: :roll: :roll: :roll: :roll: :roll: :roll:

Saurabh Goyal
[email protected]
-------------------------

EveryBody Wants to Win But Nobody wants to prepare for Win.

Like this post

goyalsau: Legendary Member; Posts: 866; Joined: Mon Aug 02, 2010 6:46 pm; Location: Gwalior, India; Thanked: 31 times

by goyalsau » Tue Jan 04, 2011 11:38 pm

Anurag@Gurome wrote:
goyalsau wrote:if n is the smallest number that leaves respective remainders of 4, 6 and 9 when divided successively by 13, 11 and 15.
The number should be written in the following ways,
1. n = 11a + 6
2. n = 13b + 4
3. n = 15c + 9
Where a, b, and c are non-negative integers.

Our job is to combine all these three to get a single expression for n, from which we can easily determine the smallest possible value.

Combining first two relation we can say (13b + 4) gives a remainder of 6 when divided by 11. Now, (13b + 4) = 11b + (2b + 4). Hence (2b + 4) also gives a remainder of 6 when divided by 11. Which again implies 2b will give a remainder of (6 - 4) = 2 when divided by 11. Hence b will give a remainder of 1 when divided by 11. Thus, b can be written as (11x + 1) for some non-negative integer x.

Sir, Till here you solved in one step. Let me rephrase what you did so for better understanding.

1. We have to write down the number in the form of 2p + 1 ( just an example ) to consider all the conditions.

2. we start by taking any two first .So what we come to a point where we get the number which satisfies the condition

3. 13b + 4, when divided by 11 remainder is 6. 11b is a multiple of 11 then 2b + 4 , must give the remainder 6, so when 2b is divided by 11 remainder should be 2, Because 4 is all ready there. as b must be in the form of 11x + 1 , so when 22x + 2 when divided by 11 remainder should be 2, so value of b must be 11x + 1

4.Like here in (143x + 17) is the number when divided by 11 remainder is 6 & when divided by 13 remainder is 4

Hence, n = 13*(11x + 1) + 4 = (143x + 17)

Anurag@Gurome wrote: Now we have to combine this with the third relation. Which clearly implies (143x + 17) will give a remainder of 9 when divided by 15. Now, (143x + 17) = (135x + 8x + 15 + 2) = 15*(9x + 1) + (8x + 2). Hence (8x + 2) also gives a remainder of 9 when divided by 15. Which again implies 8x will give a remainder of (9 - 2) = 7 when divided by 15. Thus, 8x must be of the form (15y + 7) for some non-negative integer y. Note that this means 8 divides (15y + 7) = (8y + 7y + 7) = 8y + 7(y + 1). Again this implies 8 divides 7(y + 1). Now as 8 doesn't divide 7, 8 must divide (y + 1). Thus y) must be of the form (8z + 7) for some non-negative integer z. Hence, 8x = (15y + 7) = 15*(8z + 7) + 7 = (120z + 112) = 8*(15z + 14). hence x is of the form (15z + 14) for some non-negative integer z.

Hence, n = 13*(11x + 1) + 4 = (143x + 17) = 143*(15z + 14) + 17 = (2145z + 2019)

Hence minimum possible value of n is 2019.

Sir, This second part is very confusing. I know it is of high level but there are too many steps involved. till 8x=15y+7, i was able to understand but after that you divide it by 8 , which i am not able to understand........

Saurabh Goyal
[email protected]
-------------------------

EveryBody Wants to Win But Nobody wants to prepare for Win.

Like this post

GMAT/MBA Expert

Anurag@Gurome: GMAT Instructor; Posts: 3835; Joined: Fri Apr 02, 2010 10:00 pmFollowed by: 523 members; Location: Milpitas, CA; Thanked: 1854 times; GMAT Score:770

by Anurag@Gurome » Wed Jan 05, 2011 12:01 am

goyalsau wrote:Sir, This second part is very confusing. I know it is of high level but there are too many steps involved. till 8x=15y+7, i was able to understand but after that you divide it by 8 , which i am not able to understand........

Well it is complicated.
Read the following explanation chunk by chunk.

I assume you have understood why 8x can represented as (15y + 7). If that can be done, then (15y + 7) must be divisible by 8. Is that okay with you? Then proceed and forget everything we've done till now..

Now, (15y + 7) = 8y + (7y + 7) = Multiple of 8 + 7(y + 1)
As (15y + 7) is a multiple of 8, the term in blue must be multiple of 8 too. Hence 7(y + 1) must be a multiple of 8. Now 7(y + 1) is the product of 7 and (y + 1). Thus the product will be multiple of 8 only if (y + 1) is multiple of 8. Okay? Then proceed.

(y + 1) is multiple of 8.
Therefore y must be of the form (8z + 7) for some non-negative integer z. If you don't understand why, let's pick some numbers. (y + 1) is multiple of 8 => y must be 1 less than the multiple of 8. Possible values of y are: 7, 15, 23, 31, 39 etc... All of these are of the form (8z + 7). (Note that we may also say that y is of the form (8z - 1), but it is recommended to avoid the "minus" sign in remainder problems.)

Thus, y is of the form (8z + 7) and previously 8x is of the form (15y + 7). Hence combining both of them, 8x is of the form [15*(8z + 7) + 7] = (120z + 112).

Now, 8x = (120z + 112) = [(8*15)z + (8*14)] = 8*(15z + 14)
=> x = (15z + 14)

Hence x is of the form (15z + 14).

Previously n is of the form (143x + 17)
Now combine both of them.

Like this post

goyalsau: Legendary Member; Posts: 866; Joined: Mon Aug 02, 2010 6:46 pm; Location: Gwalior, India; Thanked: 31 times

by goyalsau » Wed Jan 05, 2011 4:55 am

I may be asking too many questions. But i have already spent by full day and still not sure whether i will be able to solve a different problem on this pattern.....

First we got the value of x as (11x + 1), which was a multiple of 2, But we did not solve it beyond that

In second case we got the value of x as (15y + 7), But here we went on solve it for multiple of 8 . go get the value x as (15z + 14), Why is that so????????

Saurabh Goyal
[email protected]
-------------------------

EveryBody Wants to Win But Nobody wants to prepare for Win.

Like this post

GMAT/MBA Expert

Anurag@Gurome: GMAT Instructor; Posts: 3835; Joined: Fri Apr 02, 2010 10:00 pmFollowed by: 523 members; Location: Milpitas, CA; Thanked: 1854 times; GMAT Score:770

by Anurag@Gurome » Wed Jan 05, 2011 5:11 am

goyalsau wrote:I may be asking too many questions. But i have already spent by full day and still not sure whether i will be able to solve a different problem on this pattern.....

First we got the value of x as (11x + 1), which was a multiple of 2, But we did not solve it beyond that

In second case we got the value of x as (15y + 7), But here we went on solve it for multiple of 8 . go get the value x as (15z + 14), Why is that so????????

This is not really a GMAT type question.

If you are still interested, then proceed.

Please try to understand that our goal is to bring a or x or n in terms of multiplicative forms. Manipulating which we can find the result. To do so, we have express a or x or n in terms of other non-negative integer. If we have a relation like 8x = (15 + 7), we cannot proceed with t in this form. This is because if we directly replace this value in the expression form n in terms of x, we will end up with non-integers too. Thus we need to form a relation in which a or x or n is not multiplied with any constant.

Now note that in the first case too we have converted remainder(2b/11) = 2 to remainder(b/11) = 1. May be you have missed this because its too simple. But the second one with 8x is somewhat complicated.

As I said, this problem is not very GMAT type. If such problems occur in GMAT, they will only give two criteria not three or may be more than that but with 2, 3, 4 etc not 11, 13, 15... In which case it becomes easier to find numbers than to go into the abstract.

Like this post

aleph777: Master | Next Rank: 500 Posts; Posts: 131; Joined: Fri Jun 18, 2010 10:19 am; Location: New York, NY; Thanked: 10 times

by aleph777 » Wed Jan 05, 2011 7:34 am

GMATGuruNY wrote:
goyalsau wrote:I am not able to recall the technique by which by which we solve such problems........ Please Help Guys........

if n is the smallest number that leaves respective remainders of 4, 6 and 9 when divided successively by 13, 11 and 15.
I would simply try the answer choices -- starting with the smallest -- until I found one that satisfies all the conditions given.

I'm usually all for a deep, methodical understanding of the theory behind the problem, but in this case, I agree with GMATGuruNY! The math involved here would take so long, I'd defer to plugging in answers til I found one that worked.

Like this post

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 » Wed Jan 05, 2011 8:05 am

Find the sum of the remainders obtained when a number n is divided by 9 and 7 successively, if n is the smallest number that leaves respective remainders of 4 and 6 when divided successively by 13 and 11.

The GMAT never -- never! -- would include the original question as written.

The version quoted above is possible, although the wording likely would be different. Number probably would be replaced with positive integer. Instead of saying to divide successively, the GMAT writers probably would say that the remainder when n is divided by 13 is 4 and the remainder when n is divided by 11 is 6.

Regardless, please note that the version above can be solved quite quickly without any high-level math:

Integers that are 4 greater than multiples of 13: 17, 30, 43...
Integers that are 6 greater than multiples of 11: 17...

Done! n=17 satisfies both conditions. Now to answer the question:
17/9 = 1 R8
17/7 = 2 R3
Sum of the remainders = 8+3 = 11.

Remember, no GMAT question ever asks:

Do you understand the high-level fundamental concept behind this question?

Essentially, the only question ever asked is:

Which answer choice is correct?

The point is earned either way.

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