Oct 18 08:00 AM PDT  09:00 AM PDT Learn an intuitive, systematic approach that will maximize your success on Fillintheblank GMAT CR Questions. Oct 19 07:00 AM PDT  09:00 AM PDT Does GMAT RC seem like an uphill battle? eGMAT is conducting a free webinar to help you learn reading strategies that can enable you to solve 700+ level RC questions with at least 90% accuracy in less than 10 days. Sat., Oct 19th at 7 am PDT Oct 20 07:00 AM PDT  09:00 AM PDT Get personalized insights on how to achieve your Target Quant Score. Oct 22 08:00 PM PDT  09:00 PM PDT On Demand for $79. For a score of 4951 (from current actual score of 40+) AllInOne Standard & 700+ Level Questions (150 questions) Oct 23 08:00 AM PDT  09:00 AM PDT Join an exclusive interview with the people behind the test. If you're taking the GMAT, this is a webinar you cannot afford to miss!
Author 
Message 
TAGS:

Hide Tags

Intern
Joined: 08 Nov 2009
Posts: 2

Positive integer n leaves a remainder of 4 after division by
[#permalink]
Show Tags
Updated on: 20 Apr 2012, 03:05
Question Stats:
73% (02:02) correct 27% (02:17) wrong based on 1670 sessions
HideShow timer Statistics
Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5. If n is greater than 30, what is the remainder that n leaves after division by 30? A. 3 B. 12 C. 18 D. 22 E. 28
Official Answer and Stats are available only to registered users. Register/ Login.
Originally posted by bchekuri on 05 May 2010, 23:49.
Last edited by Bunuel on 20 Apr 2012, 03:05, edited 1 time in total.
Edited the question and added the OA




Math Expert
Joined: 02 Sep 2009
Posts: 58402

Re: Manhattan Remainder Problem
[#permalink]
Show Tags
06 May 2010, 04:18
To elaborate more. Suppose we are told that: Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 2 after division by 8. What is the remainder that n leaves after division by 12?The statement "positive integer n leaves a remainder of 4 after division by 6" can be expressed as: \(n=6p+4\). Thus according to this particular statement \(n\) could take the following values: 4, 10, 16, 22, 28, 34, 40, 46, 52, 58, 64, ... The statement "positive integer n leaves a remainder of 2 after division by 8" can be expressed as: \(n=8q+2\). Thus according to this particular statement \(n\) could take the following values: 2, 10, 18, 26, 34, 42, 50, 58, 66, ... The above two statements are both true, which means that the only valid values of \(n\) are the values which are common in both patterns. For example \(n\) can not be 16 (from first pattern) as the second formula does not give us 16 for any value of integer \(q\). So we should derive general formula (based on both statements) that will give us only valid values of \(n\). How can these two statement be expressed in one formula of a type \(n=kx+r\)? Where \(x\) is divisor and \(r\) is a remainder. Divisor \(x\) would be the least common multiple of above two divisors 6 and 8, hence \(x=24\). Remainder \(r\) would be the first common integer in above two patterns, hence \(r=10\). Therefore general formula based on both statements is \(n=24k+10\). Thus according to this general formula valid values of \(n\) are: 10, 34, 58, ... Now, \(n\) divided by 12 will give us the reminder of 10 (as 24k is divisible by 12). Hope it helps.
_________________




Manager
Joined: 30 Aug 2010
Posts: 81
Location: Bangalore, India

Re: Manhattan Remainder Problem
[#permalink]
Show Tags
29 Nov 2010, 04:40
Friends,
IT IS VERY COMMON IN GMAT to solve this kind of qtns using "NEGATIVE REMAINDER" theory.
The theory says:
if a # x is devided by y and leave the positive # r as the remainder then it can also leave negative # (ry) as the remainder.
e.g:
9 when devided by 5 leves the remainder 4 : 9=5*1+4 it can also leave the remainder 45 = 1 : 9=5*2 1
back to the original qtn: n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5 ==> n leaves a remainder of 2 (i.e. 46) after division by 6 and a remainder of 2 (i.e. 35) after division by 5 ==> n when devided by 5 and 6 leaves the same remainder 2. what is n? LCM (5,6)2 = 302 = 28 CHECK: 28 when devided by 6 leaves the remainder 4 and when devided by 5 leaves the remainder 3
However, the qtn says n > 30
so what is the nex #, > 28, that can give the said remainders when devided by 6 and 5 nothing but 28 + (some multiple of 6 and 5) as this "some multiple of 6 and 5" will not give any remainder when devided by 5 or 6 but 28 will give the required remainders.
hence n could be anything that is in the form 28 + (some multiple of 6 and 5) observe that "some multiple of 6 and 5" is always a multiple of 30 as LCM (5,6) = 30.
hence when n (i.e. 28 + some multiple of 6 and 5) is devided by 30 gives the remainder 28.
ANSWER "E"
Regards, Murali.
Kudos?




Math Expert
Joined: 02 Sep 2009
Posts: 58402

Re: Manhattan Remainder Problem
[#permalink]
Show Tags
06 May 2010, 00:22
bchekuri wrote: Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5. If n is greater than 30, what is the remainder that n leaves after division by 30? (A) 3 (B) 12 (C) 18 (D) 22 (E) 28
How to approach this Problem? Positive integer n leaves a remainder of 4 after division by 6 > \(n=6p+4\) > 4, 10, 16, 22, 28, ... Positive integer n leaves a remainder of 3 after division by 5 > \(n=5q+3\) > 3, 8, 13, 18, 23, 28, ... \(n=30k+28\)  we have 30 as lcm of 5 and 6 is 30 and we have 28 as the first common integer in the above patterns is 28. Hence remainder when positive integer n is divided by 30 is 28. Answer: E. P.S. n>30 is a redundant information.
_________________



Manager
Joined: 12 Jan 2010
Posts: 223
Schools: DukeTuck,Kelogg,Darden

Re: Manhattan Remainder Problem
[#permalink]
Show Tags
06 May 2010, 12:09
bchekuri wrote: Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5. If n is greater than 30, what is the remainder that n leaves after division by 30? (A) 3 (B) 12 (C) 18 (D) 22 (E) 28
How to approach this Problem? Once we get the concept, We can also use the options to answer faster. Since the number leaves the remainder 4 after division by 6 we know it is an even number. Only even number that leaves a remainder of 3 after being divisible by 5 has to end with 8. So narrows the options to 18 and 28. since 30+18 = 48 is divisible by 6 the answer is 30+28 = 54
_________________
Run towards the things that make you uncomfortable daily. The greatest risk is not taking risks http://gmatclub.com/forum/from690to730q50v3897356.html



Director
Joined: 03 Sep 2006
Posts: 639

Re: Manhattan Remainder Problem
[#permalink]
Show Tags
28 Nov 2010, 23:29
Possible values of n are:
n = 4, 10, 16, 22, 28, 34, 40, 46, 52, 58, ...
If R = 3 after division of 5, then possible values of n are
n = 3, 8, 13, 18, 23, 28, 33, 38, 43, 48, 53, 58, ...
Therefore according to give conditions, some possible values of n are
n = 28, 58, ...
n > 30
Let's say n = 58
58/30 gives us a remainder of : 28.



Veritas Prep GMAT Instructor
Joined: 16 Oct 2010
Posts: 9705
Location: Pune, India

Re: Manhattan Remainder Problem
[#permalink]
Show Tags
11 Jun 2012, 21:15
kuttingchai wrote: Hello Murali,
Can you please explain how will you solve following example using "NEGATIVE REMAINDER" theory discussed above? "Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 2 after division by 8. What is the remainder that n leaves after division by 12?"
Question: Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 2 after division by 8. What is the remainder that n leaves after division by 12? Solution: n = 6a + 4 (or remainder = 2) n = 8b + 2 (or remainder = 6) The negative remainder is not the same in the two cases. So don't use negative remainders here. Here are some links that discuss divisibility and remainders. The third link discusses negative remainders but you will need to go through the first two posts to understand it properly. Also, the links discuss how to solve such questions. Go through them and get back if there is a doubt. http://www.veritasprep.com/blog/2011/04 ... unraveled/http://www.veritasprep.com/blog/2011/04 ... yapplied/http://www.veritasprep.com/blog/2011/05 ... emainders/
_________________
Karishma Veritas Prep GMAT Instructor
Learn more about how Veritas Prep can help you achieve a great GMAT score by checking out their GMAT Prep Options >



Intern
Joined: 19 Jul 2009
Posts: 36
Location: baltimore, md
Schools: kellogg, booth, stern, ann arbor

Re: Manhattan Remainder Problem
[#permalink]
Show Tags
22 Jun 2010, 16:19
i would have thought the answer is c: 78. why am i wrong? i had 28 at first, but doesn't n have to be greater than 30?
_________________



Manager
Joined: 12 Aug 2010
Posts: 50
Schools: UNC KenanFlagler, IU Kelley, Emory GSB
WE 1: 5 yrs

Re: Manhattan Remainder Problem
[#permalink]
Show Tags
28 Nov 2010, 21:14
Bunuel wrote: To elaborate more.
Suppose we are told that: Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 2 after division by 8. What is the remainder that n leaves after division by 12?
The statement "positive integer n leaves a remainder of 4 after division by 6" can be expressed as: \(n=6p+4\). Thus according to this particular statement \(n\) could take the following values: 4, 10, 16, 22, 28, 34, 40, 46, 52, 58, 64, ...
The statement "positive integer n leaves a remainder of 2 after division by 8" can be expressed as: \(n=8q+2\). Thus according to this particular statement \(n\) could take the following values: 2, 10, 18, 26, 34, 42, 50, 58, 66, ...
The above two statements are both true, which means that the only valid values of \(n\) are the values which are common in both patterns. For example \(n\) can not be 16 (from first pattern) as the second formula does not give us 16 for any value of integer \(q\).
So we should derive general formula (based on both statements) that will give us only valid values of \(n\).
How can these two statement be expressed in one formula of a type \(n=kx+r\)? Where \(x\) is divisor and \(r\) is a remainder.
Divisor \(x\) would be the least common multiple of above two divisors 6 and 8, hence \(x=24\).
Remainder \(r\) would be the first common integer in above two patterns, hence \(r=10\).
Therefore general formula based on both statements is \(n=24k+10\). Thus according to this general formula valid values of \(n\) are: 10, 34, 58, ...
Now, \(n\) divided by 12 will give us the reminder of 10 (as 24k is divisible by 12).
Hope it helps. Thanks Bunuel  you are a gem.
_________________
The night is at its darkest just before the dawn... never, ever give up!



Manager
Joined: 28 Jul 2011
Posts: 159

Re: Manhattan Remainder Problem
[#permalink]
Show Tags
10 Jun 2012, 12:21
muralimba wrote: Friends,
IT IS VERY COMMON IN GMAT to solve this kind of qtns using "NEGATIVE REMAINDER" theory.
The theory says:
if a # x is devided by y and leave the positive # r as the remainder then it can also leave negative # (ry) as the remainder.
e.g:
9 when devided by 5 leves the remainder 4 : 9=5*1+4 it can also leave the remainder 45 = 1 : 9=5*2 1
back to the original qtn: n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5 ==> n leaves a remainder of 2 (i.e. 46) after division by 6 and a remainder of 2 (i.e. 35) after division by 5 ==> n when devided by 5 and 6 leaves the same remainder 2. what is n? LCM (5,6)2 = 302 = 28 CHECK: 28 when devided by 6 leaves the remainder 4 and when devided by 5 leaves the remainder 3
However, the qtn says n > 30
so what is the nex #, > 28, that can give the said remainders when devided by 6 and 5 nothing but 28 + (some multiple of 6 and 5) as this "some multiple of 6 and 5" will not give any remainder when devided by 5 or 6 but 28 will give the required remainders.
hence n could be anything that is in the form 28 + (some multiple of 6 and 5) observe that "some multiple of 6 and 5" is always a multiple of 30 as LCM (5,6) = 30.
hence when n (i.e. 28 + some multiple of 6 and 5) is devided by 30 gives the remainder 28.
ANSWER "E"
Regards, Murali.
Kudos? Hello Murali, Can you please explain how will you solve following example using "NEGATIVE REMAINDER" theory discussed above? "Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 2 after division by 8. What is the remainder that n leaves after division by 12?"



Veritas Prep GMAT Instructor
Joined: 16 Oct 2010
Posts: 9705
Location: Pune, India

Re: Positive integer n leaves a remainder of 4 after division by
[#permalink]
Show Tags
14 Apr 2014, 00:08
Saabs wrote: Maybe I did something wrong, or I just got lucky, so please inform me. I also had 28 as the solution, by just plugging in the values. a. 3 / 6 = 0 r 6 INCORRECT b. 12 / 6 = 2 r 0 INCORRECT c. 18 / 6 = 3 r 0 INCORRECT d. 22 / 6 = 3 r 4 & 22 / 5 = 4 r 2 INCORRECT e. 28 / 6 = 4 r 4 & 28 / 5 = 4 r 3 CORRECTSupersimple math, so there must be something wrong here, haha. What you did is correct. The reason you did it will tell you whether you got lucky or used good reasoning. The question tells you that "n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5" The options are not the values of n; they are the values of remainder that is leftover after you divide n by 30. You divided the options by 6 and 5 and got the remainder as 4 and 3 respectively. Was that a mistake you made? If yes, then you got lucky. Though, if you had used logic and said, "Ok, so when n is divided by 30, groups of 30 are made. What is leftover is given in the options. 30 is completely divisible by 6 and by 5 hence the groups of 30 can be evenly divided into groups of 6 as well as groups of 5. So whatever is leftover after division by 30, we need to split that into further groups of 6 and 5. When we split it into groups of 6, we must have remainder as 4 since n leaves remainder 4. When we split it into groups of 5, we must have remainder as 3 since n leaves remainder 3. And, if that is the reason you divided the options by 6 and 5, checked their remainders and got your answer, then well done! You got the logic!"
_________________
Karishma Veritas Prep GMAT Instructor
Learn more about how Veritas Prep can help you achieve a great GMAT score by checking out their GMAT Prep Options >



Manager
Joined: 17 Mar 2014
Posts: 122
Location: United States
Concentration: Entrepreneurship, Leadership
GPA: 3.97

Re: Manhattan Remainder Problem
[#permalink]
Show Tags
17 Apr 2014, 12:12
Bunuel wrote: To elaborate more.
Suppose we are told that: Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 2 after division by 8. What is the remainder that n leaves after division by 12?
The statement "positive integer n leaves a remainder of 4 after division by 6" can be expressed as: \(n=6p+4\). Thus according to this particular statement \(n\) could take the following values: 4, 10, 16, 22, 28, 34, 40, 46, 52, 58, 64, ... The statement "positive integer n leaves a remainder of 2 after division by 8" can be expressed as: \(n=8q+2\). Thus according to this particular statement \(n\) could take the following values: 2, 10, 18, 26, 34, 42, 50, 58, 66, ...
The above two statements are both true, which means that the only valid values of \(n\) are the values which are common in both patterns. For example \(n\) can not be 16 (from first pattern) as the second formula does not give us 16 for any value of integer \(q\).
So we should derive general formula (based on both statements) that will give us only valid values of \(n\).
How can these two statement be expressed in one formula of a type \(n=kx+r\)? Where \(x\) is divisor and \(r\) is a remainder.
Divisor \(x\) would be the least common multiple of above two divisors 6 and 8, hence \(x=24\).
Remainder \(r\) would be the first common integer in above two patterns, hence \(r=10\).
Therefore general formula based on both statements is \(n=24k+10\). Thus according to this general formula valid values of \(n\) are: 10, 34, 58, ...
Now, \(n\) divided by 12 will give us the reminder of 10 (as 24k is divisible by 12).
Hope it helps. Bunuel – very good explanation. First case  i). given statement in a question is  Remainder is 7 when positive integer n is divided by 18. And ii). if we are asked to find out the remainder when n is divided by 6, Then since 18 is completely divisible by 6 or 6 is a factor of 18, we can find out the solution easily by above given statement. As, n = 18 q + 7; 18 is completely divisible by 6, thus no remainder exists when 18q/6 and when 7 is divided by 6, it would yield 1 as the remainder. Second case i). given statement in a question is  Remainder is 7 when positive integer n is divided by 18. And ii). if we are asked to find out the remainder when n is divided by 8, Then since 18 is not divisible by 8 or 8 is not a factor of 18, we cannot find out the solution by above given statement. Third case i). given statement in a question is  Remainder is 7 when positive integer n is divided by 6. And ii). if we are asked to find out the remainder when n is divided by 12, Then since 6 is not divisible by 12, however it true the other way round. We cannot find out the solution by above given statement. Fourth case, which you have explained – “Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 2 after division by 8. What is the remainder that n leaves after division by 12?” We have two given statements – since one statement will not yield us the answer as explained in my earlier three cases. But, since we have two given statements which derive – n = 6Q1 + 4 & n = 8Q2 + 2. Q1, Q2 are quotients respectively. And if we look at 6Q1 and 8 Q2, the LCM yields 24. Since we are asked the remainder when division is done by 12 and since 12 is completely divisible by 24. Thus, we can come up with a solution. Otherwise we cannot. I hope I was able to explain what I wanted to and the above conclusion described in the 4 cases is correct.
_________________
KUDOS!!!, I need them too



Veritas Prep GMAT Instructor
Joined: 16 Oct 2010
Posts: 9705
Location: Pune, India

Re: Positive integer n leaves a remainder of 4 after division by
[#permalink]
Show Tags
01 Jun 2014, 20:56
bhatiavai wrote: Hi, Probably a silly question.... But can some one explain why Remainder r would be the first common integer in the two patterns n=6p+4 n=5q+3
Many Thanks N is of the form 6p+4 which means it is one of 4, 10, 16, 22, 28, ... N is also of the form 5q+3 which means it must also be one of 3, 8, 13, 18, 23, 28, ... Since N must be a value in both the lists, N can take the values common to both. The first such value is 28. So N can be 28. Now what other values can N take? 28 is a number that will leave a remainder of 4 when divided by 6 and a remainder of 3 when divided by 5. The next such number will be (LCM of 6 and 5) + 28. Why? because whatever you add to 28, that should be divisible by 6 as well as 5. Then whatever you add will have no relevance to the remainder and the remainders will remain the same. That is why some other values of N will be 30+28, 60+28 ...etc. After you divide any of these numbers by 30, the remainder will be 28. For more on divisibility and remainders, check: http://www.veritasprep.com/blog/2011/04 ... unraveled/http://www.veritasprep.com/blog/2011/04 ... yapplied/http://www.veritasprep.com/blog/2011/05 ... emainders/http://www.veritasprep.com/blog/2011/05 ... spartii/Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5. If n is greater than 30, what is the remainder that n leaves after division by 30?
_________________
Karishma Veritas Prep GMAT Instructor
Learn more about how Veritas Prep can help you achieve a great GMAT score by checking out their GMAT Prep Options >



Veritas Prep GMAT Instructor
Joined: 16 Oct 2010
Posts: 9705
Location: Pune, India

Re: Positive integer n leaves a remainder of 4 after division by
[#permalink]
Show Tags
05 Feb 2015, 20:56
tieurongthieng wrote: Hi Karishma, could you kindly explain the bold part? I have trouble understanding why it was the case.. You might want to check out this post first on divisibility and remainders: http://www.veritasprep.com/blog/2011/04 ... unraveled/This tells you why when you divide a number by 30 and get, say 4 as remainder, you will get 4 as remainder when you divide the same number by 6 or 5 or 10 or 15 (factors of 30 greater than 4). After that, you should check out this post which discusses this particular question in detail: http://www.veritasprep.com/blog/2014/05 ... thegmat/I think these two together will help you get a very clear picture.
_________________
Karishma Veritas Prep GMAT Instructor
Learn more about how Veritas Prep can help you achieve a great GMAT score by checking out their GMAT Prep Options >



Veritas Prep GMAT Instructor
Joined: 16 Oct 2010
Posts: 9705
Location: Pune, India

Re: Positive integer n leaves a remainder of 4 after division by
[#permalink]
Show Tags
09 Mar 2015, 20:13
khl52 wrote: My question was WHY would it be that "divisor would be the LCM of two divisors 6 and 8" and WHY would it be that the remainder would be first of the common integers? I am having some trouble making the jump in that logic and would appreciate your help. Thanks again! To understand the 'why' of divisibility and remainders, check out these posts in this order: http://www.veritasprep.com/blog/2011/04 ... unraveled/http://www.veritasprep.com/blog/2011/04 ... yapplied/http://www.veritasprep.com/blog/2011/05 ... emainders/http://www.veritasprep.com/blog/2011/05 ... spartii/
_________________
Karishma Veritas Prep GMAT Instructor
Learn more about how Veritas Prep can help you achieve a great GMAT score by checking out their GMAT Prep Options >



Veritas Prep GMAT Instructor
Joined: 16 Oct 2010
Posts: 9705
Location: Pune, India

Re: Positive integer n leaves a remainder of 4 after division by
[#permalink]
Show Tags
03 May 2015, 21:27
vikasbansal227 wrote: Dear All,
Its difficult that on what basis we took "First common integer in two patterns" as a remainder for the formula?
Can someone please explain,
Thanks You want a number, n, that satisfies two conditions: "leaves a remainder of 4 after division by 6" and "a remainder of 2 after division by 8" So you find the first such number by writing down the numbers. You get that it is 10. 10 satisfies both conditions. What will be the next number? Any number that is a multiple of 6 more than 10 will continue to satisfy the first condition. e.g. 16, 22, 28, 34 etc Any number that is a multiple of 8 more than 10 will continue to satisfy the second condition. e.g. 18, 26, 34 etc So any number that is a multiple of both 6 and 8 more than 10 will satisfy both conditions. LCM of 6 and 8 is 24. 24 is divisible by both 6 and 8. So any number that is a multiple of 24 more than 10 will satisfy both conditions. e.g. 34, 58 .. etc These numbers can be written as 10 + 24a. Also, I think you did not check out the 4 links I gave here: positiveintegernleavesaremainderof4afterdivisionby9375240.html#p1496547They are very useful in understanding divisibility fundamentals.
_________________
Karishma Veritas Prep GMAT Instructor
Learn more about how Veritas Prep can help you achieve a great GMAT score by checking out their GMAT Prep Options >



VP
Joined: 07 Dec 2014
Posts: 1222

Positive integer n leaves a remainder of 4 after division by
[#permalink]
Show Tags
19 May 2018, 11:33
bchekuri wrote: Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5. If n is greater than 30, what is the remainder that n leaves after division by 30?
A. 3 B. 12 C. 18 D. 22 E. 28 let q and p be quotients 6q+4=5p+3➡ 5p6q=1 because 6q can't have digits unit of 9, 5p must have units digit of 5, and therefore 6q must have digits unit of 4 thus, 5p=25 and 6q=24, least values of p and q are 5 and 4 respectively, and least value of n=28 28/30 leaves a remainder of 28 E



Manager
Joined: 30 May 2018
Posts: 70
Concentration: General Management, Marketing
GPA: 3.45
WE: Other (Retail)

Positive integer n leaves a remainder of 4 after division by
[#permalink]
Show Tags
11 Oct 2018, 07:43
#MY10SECAPPROACH : Just see the options , the answer options are remainders given , just divide them with 5 & 6 to see which one satisfies the condition of leaving remainder 3 and 4 respectively. Only 1 , answer option E. Time taken : 10 Seconds. Kudos ?
_________________
Kudos if you agree , Comment if you don't !!!



Manager
Joined: 22 Dec 2011
Posts: 211

Re: Manhattan Remainder Problem
[#permalink]
Show Tags
12 Sep 2012, 22:24
Bunuel wrote: To elaborate more.
Suppose we are told that: Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 2 after division by 8. What is the remainder that n leaves after division by 12?
The statement "positive integer n leaves a remainder of 4 after division by 6" can be expressed as: \(n=6p+4\). Thus according to this particular statement \(n\) could take the following values: 4, 10, 16, 22, 28, 34, 40, 46, 52, 58, 64, ... The statement "positive integer n leaves a remainder of 2 after division by 8" can be expressed as: \(n=8q+2\). Thus according to this particular statement \(n\) could take the following values: 2, 10, 18, 26, 34, 42, 50, 58, 66, ...
The above two statements are both true, which means that the only valid values of \(n\) are the values which are common in both patterns. For example \(n\) can not be 16 (from first pattern) as the second formula does not give us 16 for any value of integer \(q\).
So we should derive general formula (based on both statements) that will give us only valid values of \(n\).
How can these two statement be expressed in one formula of a type \(n=kx+r\)? Where \(x\) is divisor and \(r\) is a remainder.
Divisor \(x\) would be the least common multiple of above two divisors 6 and 8, hence \(x=24\).
Remainder \(r\) would be the first common integer in above two patterns, hence \(r=10\).
Therefore general formula based on both statements is \(n=24k+10\). Thus according to this general formula valid values of \(n\) are: 10, 34, 58, ...
Now, \(n\) divided by 12 will give us the reminder of 10 (as 24k is divisible by 12).
Hope it helps. This is awesome I was searching for this logic for a long time. Just one question  you said, i quote, Remainder \(r\) would be the first common integer in above two patterns, hence \(r=10\). Is there a quick way to come with this value without listing the nos out. sometime the common nos in both the series would come after 6 or 7 term hence sometimes consumes time. Is there a quicker way? My sincere thanks. cheers



Math Expert
Joined: 02 Sep 2009
Posts: 58402

Re: Manhattan Remainder Problem
[#permalink]
Show Tags
13 Sep 2012, 04:59
Jp27 wrote: Bunuel wrote: To elaborate more.
Suppose we are told that: Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 2 after division by 8. What is the remainder that n leaves after division by 12?
The statement "positive integer n leaves a remainder of 4 after division by 6" can be expressed as: \(n=6p+4\). Thus according to this particular statement \(n\) could take the following values: 4, 10, 16, 22, 28, 34, 40, 46, 52, 58, 64, ... The statement "positive integer n leaves a remainder of 2 after division by 8" can be expressed as: \(n=8q+2\). Thus according to this particular statement \(n\) could take the following values: 2, 10, 18, 26, 34, 42, 50, 58, 66, ...
The above two statements are both true, which means that the only valid values of \(n\) are the values which are common in both patterns. For example \(n\) can not be 16 (from first pattern) as the second formula does not give us 16 for any value of integer \(q\).
So we should derive general formula (based on both statements) that will give us only valid values of \(n\).
How can these two statement be expressed in one formula of a type \(n=kx+r\)? Where \(x\) is divisor and \(r\) is a remainder.
Divisor \(x\) would be the least common multiple of above two divisors 6 and 8, hence \(x=24\).
Remainder \(r\) would be the first common integer in above two patterns, hence \(r=10\).
Therefore general formula based on both statements is \(n=24k+10\). Thus according to this general formula valid values of \(n\) are: 10, 34, 58, ...
Now, \(n\) divided by 12 will give us the reminder of 10 (as 24k is divisible by 12).
Hope it helps. This is awesome I was searching for this logic for a long time. Just one question  you said, i quote, Remainder \(r\) would be the first common integer in above two patterns, hence \(r=10\). Is there a quick way to come with this value without listing the nos out. sometime the common nos in both the series would come after 6 or 7 term hence sometimes consumes time. Is there a quicker way? My sincere thanks. cheers In some cases we can use some other approaches, though I think simple listing is the easiest way.
_________________




Re: Manhattan Remainder Problem
[#permalink]
13 Sep 2012, 04:59



Go to page
1 2 3 4
Next
[ 62 posts ]



