8. What is the smallest positive integer that leaves a remainder of 1 when divided by 2, remainder of 2 when divided by 3, a remainder of 3 when divided by 4, and so on up to a remainder of 9 when divided by 10? The answer to this, (along with #9 & #16,) was sent to me by Dave Blackston who visited me from fark.com (then corrected by Daya Chand)... Before reading the answer can I interest you in a clue? The key to this is to realise that if a number N (eg 104) is to leave a remainder, say 4 when divided by 5 then N + 1 (ie 105) is exactly divisible by 5, similarly if a number (eg 87) is to leave a remainder 7 when divided by 8 then N + 1 (ie 88) is exactly divisible by 8:- Therefore in our question N + 1 is divisible by 2, 3, 4, 5, 6, 7, 8, 9 & 10 There is a tool here you can use to try different values of N Note: no information is sent to me, the calculation is done entirely locally, on your computer. Meaning N+1 is 2000 N+1 has the following factors:2✓ 3✗ 4✓ 5✓ 6✗ 7✗ 8✓ 9✗ 10✓ All Factors✗ The lowest value for N + 1 is 2520, which means the lowest value for N is:- 2519 How do we arrive at N + 1 = 2520?As stated N + 1 is divisible by 2, 3, 4, 5, 6, 7, 8, 9 & 10 so clearly one solution would be 10! (ie 10*9*8*7*6*5*4*3*2 = 3628800 for N +1) but this is not the lowest possible. Follow the logic below... N + 1 must be a multiple of 2 N + 1 must be a multiple of 4 but if it is a multiple of 2 & 4 it is necessarily a multiple of 8 N + 1 must be a multiple of 5 but if it is a multiple of 2 & 5 it is necessarily a multiple of 10 N + 1 must be a multiple of 6 but if it is a multiple of 2 & 9 (18) it is necessarily a multiple of 6 N + 1 must be a multiple of 7 N + 1 must be a multiple of 9Hence 2 x 4 x 5 x 7 x 9 = 2520 is a multiple of 2, 3, 4, 5, 6, 7, 8, 9 & 10 Mathematically the process we are dealing with here is known as lowest or least common multiple. Where next? List of Puzzles Random Puzzle Next Puzzle © Nigel Coldwell 2004 - – The questions on this site may be reproduced without further permission, I do not claim copyright over them. The answers are mine and may not be reproduced without my expressed prior consent. Please inquire using the link at the top of the page. Secure version of this page.
Math Expert Joined: 02 Sep 2009 Posts: 87818
REMAINDERS [#permalink]
REMAINDERS This post is a part of [GMAT MATH BOOK] created by: Bunuel edited by: bb, Bunuel-------------------------------------------------------- Definition If \(x\) and \(y\) are positive integers, there exist unique integers \(q\) and \(r\), called the quotient and remainder, respectively, such that \(y =divisor*quotient+remainder= xq + r\) and \(0\leq{r}<x\). For example, when 15 is divided by 6, the quotient is 2 and the remainder is 3 since \(15 = 6*2 + 3\).Notice that \(0\leq{r}<x\) means that remainder is a non-negative integer and always less than divisor. This formula can also be written as \(\frac{y}{x} = q + \frac{r}{x}\).Properties
Example #1 (easy) If the remainder is 7 when positive integer n is divided by 18, what is the remainder when n is divided by 6? A. 0B. 1C. 2D. 3E. 4When positive integer n is dived by 18 the remainder is 7: \(n=18q+7\).Now, since the first term (18q) is divisible by 6, then the remainder will only be from the second term, which is 7. 7 divided by 6 yields the remainder of 1.Answer: B. Discuss this question HERE. Example #2 (easy) If n is a prime number greater than 3, what is the remainder when n^2 is divided by 12 ? A. 0B. 1C. 2D. 3E. 5There are several algebraic ways to solve this question, but the easiest way is as follows: since we cannot have two correct answers just pick a prime greater than 3, square it and see what would be the remainder upon division of it by 12. If \(n=5\), then \(n^2=25\). The remainder upon division 25 by 12 is 1.Answer: B. Discuss this question HERE. Example #3 (easy) What is the tens digit of positive integer x ? (1) x divided by 100 has a remainder of 30.(2) x divided by 110 has a remainder of 30.(1) x divided by 100 has a remainder of 30. We have that \(x=100q+30\): 30, 130, 230, ... as you can see every such number has 3 as the tens digit. Sufficient.(2) x divided by 110 has a remainder of 30. We have that \(x=110p+30\): 30, 140, 250, 360, ... so, there are more than 1 value of the tens digit possible. Not sufficient.Answer: A. Discuss this question HERE. Example #4 (easy) What is the remainder when the positive integer n is divided by 6? (1) n is multiple of 5(2) n is a multiple of 12(1) n is multiple of 5. If n=5, then n yields the remainder of 5 when divided by 6 but if n=10, then n yields the remainder of 4 when divided by 6. We already have two different answers, which means that this statement is not sufficient.(2) n is a multiple of 12. Every multiple of 12 is also a multiple of 6, thus n divided by 6 yields the remainder of 0. Sufficient.Answer: B. Discuss this question HERE. Example #5 (medium) If s and t are positive integers such that s/t = 64.12, which of the following could be the remainder when s is divided by t ? A. 2B. 4 C. 8 D. 20 E. 45\(s\) divided by \(t\) yields the remainder of \(r\) can always be expressed as: \(\frac{s}{t}=q+\frac{r}{t}\) (which is the same as \(s=qt+r\)), where \(q\) is the quotient and \(r\) is the remainder. Given that \(\frac{s}{t}=64.12=64\frac{12}{100}=64\frac{3}{25}=64+\frac{3}{25}\), so according to the above \(\frac{r}{t}=\frac{3}{25}\), which means that \(r\) must be a multiple of 3. Only option E offers answer which is a multiple of 3Answer. E. Discuss this question HERE. Example #6 (medium) 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. 3B. 12C. 18D. 22E. 28Positive integer n leaves a remainder of 4 after division by 6: \(n=6p+4\). Thus n could be: 4, 10, 16, 22, 28, ... Positive integer n leaves a remainder of 3 after division by 5: \(n=5q+3\). Thus n could be: 3, 8, 13, 18, 23, 28, ... There is a way to derive general formula for \(n\) (of a type \(n=mx+r\), where \(x\) is a divisor and \(r\) is a remainder) based on above two statements: Divisor \(x\) would be the least common multiple of above two divisors 5 and 6, hence \(x=30\).Remainder \(r\) would be the first common integer in above two patterns, hence \(r=28\).Therefore general formula based on both statements is \(n=30m+28\). Hence the remainder when positive integer n is divided by 30 is 28.Answer. E. Discuss this question HERE. Example #7 (medium) If x^3 - x = n and x is a positive integer greater than 1, is n divisible by 8? (1) When 3x is divided by 2, there is a remainder.(2) x = 4y + 1, where y is an integer.\(x^3-x=x(x^2-1)=(x-1)x(x+1)\), notice that we have the product of three consecutive integers. Now, notice that if \(x=odd\), then \(x-1\) and \(x+1\) are consecutive even integers, thus one of them will also be divisible by 4, which will make \((x-1)(x+1)\) divisible by 2*4=8 (basically if \(x=odd\) then \((x-1)x(x+1)\) will be divisible by 8*3=24).(1) When 3x is divided by 2, there is a remainder. This implies that \(3x=odd\), which means that \(x=odd\). Therefore \((x-1)x(x+1)\) is divisible by 8. Sufficient.(2) x = 4y + 1, where y is an integer. We have that \(x=even+odd=odd\), thus \((x-1)x(x+1)\) is divisible by 8. Sufficient.Answer: D. Discuss this question HERE. Example #8 (hard) When 51^25 is divided by 13, the remainder obtained is: A. 12B. 10C. 2D. 1E. 0\(51^{25}=(52-1)^{25}\), now if we expand this expression all terms but the last one will have \(52=13*4\) in them, thus will leave no remainder upon division by 13, the last term will be \((-1)^{25}=-1\). Thus the question becomes: what is the remainder upon division -1 by 13? The answer to this question is 12: \(-1=13*(-1)+12\).Answer: A. Discuss this question HERE. Example #9 (hard) When positive integer x is divided by 5, the remainder is 3; and when x is divided by 7, the remainder is 4. When positive integer y is divided by 5, the remainder is 3; and when y is divided by 7, the remainder is 4. If x > y, which of the following must be a factor of x - y? A. 12B. 15C. 20D. 28E. 35When the positive integer x is divided by 5 and 7, the remainder is 3 and 4, respectively: \(x=5q+3\) (x could be 3, 8, 13, 18, 23, ...) and \(x=7p+4\) (x could be 4, 11, 18, 25, ...). We can derive general formula based on above two statements the same way as for the example above: Divisor will be the least common multiple of above two divisors 5 and 7, hence 35.Remainder will be the first common integer in above two patterns, hence 18. So, to satisfy both this conditions x must be of a type \(x=35m+18\) (18, 53, 88, ...);The same for y (as the same info is given about y): \(y=35n+18\);\(x-y=(35m+18)-(35n+18)=35(m-n)\). Thus \(x-y\) must be a multiple of 35.Answer: E. Discuss this question HERE. Example #10 (hard) If p, x, and y are positive integers, y is odd, and p = x^2 + y^2, is x divisible by 4? (1) When p is divided by 8, the remainder is 5(2) x – y = 3(1) When p is divided by 8, the remainder is 5. This implies that \(p=8q+5=x^2+y^2\). Since given that \(y=odd=2k+1\), then \(8q+5=x^2+(2k+1)^2\) --> \(x^2=8q+4-4k^2-4k=4(2q+1-k^2-k)\).So, \(x^2=4(2q+1-k^2-k)\). Now, if \(k=odd\) then \(2q+1-k^2-k=even+odd-odd-odd=odd\) and if \(k=even\) then \(2q+1-k^2-k=even+odd-even-even=odd\), so in any case \(2q+1-k^2-k=odd\) --> \(x^2=4*odd\) --> in order \(x\) to be multiple of 4 \(x^2\) must be multiple of 16 but as we see it's not, so \(x\) is not multiple of 4. Sufficient.(2) x – y = 3 --> \(x-odd=3\) --> \(x=even\) but not sufficient to say whether it's multiple of 4.Answer: A. Discuss this question HERE. Example #11 (hard) \(m\) and \(n\) are positive integers. Is the remainder of \(\frac{10^m + n}{3}\) bigger than the remainder of \(\frac{10^n + m}{3}\) ? (1) \(m \gt n\).(2) The remainder of \(\frac{n}{3}\) is 2First of all any positive integer can yield only three remainders upon division by 3: 0, 1, or 2.Since, the sum of the digits of \(10^m\) and \(10^n\) is always 1 then the remainders of \(\frac{10^m + n}{3}\) and \(\frac{10^n + m}{3}\) are only dependent on the value of the number added to \(10^m\) and \(10^n\). There are 3 cases:If the number added to them is: 0, 3, 6, 9, ... then the remainder will be 1 (as the sum of the digits of \(10^m\) and \(10^n\) will be 1 more than a multiple of 3);If the number added to them is: 1, 4, 7, 10, ... then the remainder will be 2 (as the sum of the digits of \(10^m\) and \(10^n\) will be 2 more than a multiple of 3);If the number added to them is: 2, 5, 8, 11, ... then the remainder will be 0 (as the sum of the digits of \(10^m\) and \(10^n\) will be a multiple of 3).(1) \(m \gt n\). Not sufficient.(2) The remainder of \(\frac{n}{3}\) is \(2\) --> \(n\) is: 2, 5, 8, 11, ... so we have the third case. Which means that the remainder of \(\frac{10^m + n}{3}\) is 0. Now, the question asks whether the remainder of \(\frac{10^m + n}{3}\), which is 0, greater than the reminder of \(\frac{10^n + m}{3}\), which is 0, 1, or 2. Obviously it cannot be greater, it can be less than or equal to. So, the answer to the question is NO. Sufficient. Answer: B. Discuss this question HERE. ______________________________________________Check more DS questions on remainders HERE. Check more PS questions on remainders HERE. Edit: For more on REMAINDERS check HERE. _________________
Originally posted by Bunuel on 24 Dec 2012, 07:48. Updated.
Math Expert Joined: 02 Sep 2009 Posts: 87818
Re: REMAINDERS [#permalink]
Intern Joined: 27 Aug 2014 Posts: 26 GMAT Date: 09-27-2014
Re: REMAINDERS [#permalink] I would like to add the following shortcuts:1)Remainder of (ax + 1)^n / a = 1Example: 46^3578 / 9 will have a remainder of 1.2)Similarly, remainder of (ax - 1)^n / a = 1 (if n is even) or -1 (if n is odd) Example: 27^79 / 14 will have a remainder of -1 or 13.
Intern Joined: 10 Mar 2013 Posts: 10
Re: REMAINDERS [#permalink] I have reviewed this theory but am still having a hard time understanding a couple of things. I will be using the following 2 examples:Example #1 & 6.From Example 1: "Now, since the first term (18q) is divisible by 6, then the remainder will only be from the second term, which is 7. 7 divided by 6 yields the remainder of 1." I don't understand why it matters if 18q is divisible by 6 or not and how do you determine if the remainder comes from the second term or not.From Example 2: Why are we trying to derive an LCM of 5 & 6? Greatly appreciate the assistance.
Math Expert Joined: 02 Sep 2009 Posts: 87818
Re: REMAINDERS [#permalink]
farhanabad wrote: I have reviewed this theory but am still having a hard time understanding a couple of things. I will be using the following 2 examples:Example #1 & 6.From Example 1: "Now, since the first term (18q) is divisible by 6, then the remainder will only be from the second term, which is 7. 7 divided by 6 yields the remainder of 1." I don't understand why it matters if 18q is divisible by 6 or not and how do you determine if the remainder comes from the second term or not.From Example 2: Why are we trying to derive an LCM of 5 & 6? Greatly appreciate the assistance. 18q can be divided equally into 6 groups, so it will leave the remainder of 0. So, the remainder when 18q+1 is divided by 6 will come only from the second term, which is 1. For example: 18 + 1 = 19 divided by 6 gives the remainder of 1;18*2 + 1 = 37 divided by 6 gives the remainder of 1;18*3 + 1 = 55 divided by 6 gives the remainder of 1;...Hope it's clear. _________________
Intern Joined: 27 Aug 2014 Posts: 26 GMAT Date: 09-27-2014
Re: REMAINDERS [#permalink] Another tip which may be handy.(Fermat's theorem)If ‘p’ is a prime number and ‘a’ and ‘p’ are co-primes:1)Remainder of (a^p)/p = a(a^p – a) will be divisible by p.Example: remainder of (10^13)/13 = 132)Remainder of [a^(p-1)]/p = 1 Example: remainder of (10^12)/13 = 1
Re: REMAINDERS [#permalink] Alternative solution to #6 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. 3B. 12C. 18D. 22 E. 28 We have -1) n - 4 = 6t and 2) n - 3 = 5kWe need to find3) n - R = 30x Multiply (1) by 5 and (2) by 61) 5n - 20 = 30t2) 6n - 18 = 30k(2) - (1)n + 2 = 30(t - k)t and k are positive integers. So we can assume them as x fro m(3)Thus R = -2 or 30-2 = 28.Answer E. +Kudos, if this helped
Intern Joined: 02 Jul 2016 Posts: 17
Re: REMAINDERS [#permalink] Hi Bunuel,the second point under properties violates example 9, i.e. when a small integer is divided by a larger one, the quotient is 0 and the remainder is the smaller number. Abhishek
Math Expert Joined: 02 Sep 2009 Posts: 87818
Re: REMAINDERS [#permalink]
abhi1693 wrote: Hi Bunuel,the second point under properties violates example 9, i.e. when a small integer is divided by a larger one, the quotient is 0 and the remainder is the smaller number. Abhishek Those properties are for positive integers. _________________
Intern Joined: 22 Jun 2015 Posts: 7
Re: REMAINDERS [#permalink] Hey, what will be the reminder when any positive integer is divided by 0?
Math Expert Joined: 02 Sep 2009 Posts: 87818
Re: REMAINDERS [#permalink]
disharupani wrote: Hey, what will be the reminder when any positive integer is divided by 0? Division by 0 is not allowed. Anything/0 is undefined. _________________
Intern Joined: 22 Jun 2015 Posts: 7
Re: REMAINDERS [#permalink] Hey sorry, wrong question what will be the reminder when 0 is divided by any positive integer? Posted from my mobile device
Math Expert Joined: 02 Sep 2009 Posts: 87818
Re: REMAINDERS [#permalink]
disharupani wrote: Hey sorry, wrong question what will be the reminder when 0 is divided by any positive integer? Posted from my mobile device 0 is divisible by every integer except 0 itself: 0/(non-zero integer) = 0 = integer, so the remainder will be 0. _________________
Manager Joined: 20 Feb 2017 Posts: 176 Location: India Concentration: Operations, Strategy WE:Engineering (Other)
Re: REMAINDERS [#permalink] How to find reminder using cyclic method : step 1: 14/11 gives us a reminder of 3 so basically the question becomes : 3^77/11Step 2: 3/11 gives us a reminder of 33^2/11 gives us a reminder of 9 3^3/11 gives us a reminder of 5 3^4/11 gives us a reminder of 4 ( easy way to calculate reminder : 3^4/11 = 3^3/11*3 = 5*3/11 =4 )3^5 /11 gives us a reminder of 1 ( similarly 3^5/11 = 4*3/11 =12/11=1)Whenever we get a reminder of 1 , we get our cyclic value. Here in this case the cyclicity is 5Step 3 Divide the power with the cyclic value77/5 which gives us a reminder of 2. Thus the reminder of the expression 14^77/11 is the second term of cycle. Here it is 9Q2. Find the reminder of the expression 4^98/25here since the numerator is small than denominator we go directly to cycle4^1/25 gives us a reminder of 44^2/25 gives us a reminder of 164^3/25 gives us a reminder of 14 (16*4/25 =14)4^4/25 gives us a reminder of 6 (14*4/25 =6)4^5/25 gives us a reminder of 24 or -1 (6*4/25=24 or -1)Whenever we have a reminder of -1 , then the cycle would be double of its position. Here at 5th position the reminder becomes -1, hence the cyclicity would be 10)divide the power with the cycle number98/10 , this gives a reminder of 8hence 8th term of the cycle is the reminder for the expression. (to find the 8th term : 4^4*4^4/25 = 6*6/25 =11)Hence 11 is the answer.Another method for peculiar cases Q3. 2^300/9 find the reminder2^300/9 can be written as (2^3)^100/9 or 8^100/9 or (-1)^100/9 = 1/9 or the reminder is 1 Q4. 12^175/13. Find the reminderwe can write this as (-1)^175/13 or -1/13 . Hence the reminder would be 12Q5. find the reminder of 14^21^39/11take 21^39 as N, the expression becomes 14^N/1114/11 gives a reminder of 3 , hence the expression becomes 3^N/11so continuing with cycle3/11 gives us a reminder of 33^2/11 gives us a reminder of 93^3/11 gives us a reminder of 53^4/11 gives us a reminder of 43^5/11 gives us a reminder of 1 Hence the cyclicity is 5so we need to divide the power by cycle21^39/521/5 gives a reminder of 1so the21^39/5 expression becomes 1^39/5 . the reminder is 1hence the reminder of 14^21^39/11 is the first term of the cycle or 3Hence the reminder is 3Q6. Find the reminder of 17^100/51 if we look closely we will find 51 is divisible by 17.So take one 17 out and keep outside. The expression becomes17 * REM[17^99/3]or 17 * REM[ (-1)^99/3]or 17*2 = 34 (answer)Q7. Find the reminder of 30^40/1730/17 gives us a reminder of 13hence the expression becomes13^40/1713^1/17 gives us a reminder of 1313^2/17 gives us a reminder of -1 or 16.Hence the cycle must be 4Divide the power with cycle 40/4 gives us a reminder of 0Hence it should be the last term of the cycle The 4th term can be found out by : 13^2*13^2/17 or (-1)*(-1)/17 or 1/17 or 1Hence the answer should be 1Q8. find the reminder of 73^382/100we can write the above expression as (73^2)^191/100or (5329)^191/100 In other words we are asked to find the last 2 digit the expression becomes 29^191/100 (we are only concerned with last 2 digit .)or (-1+30)^191/100Using binomial expression 191C0*(-1)^191*30^0+ 191C1*(-1)^190*30^1 +......= -1+ 191*30= -1+ 5730= 5729or the last 2 digit/ reminder is 29May be some cases are unwarranted for GMAT and i would recommend what @bunnel advised as the best method to go for reminders.
Intern Joined: 26 Aug 2020 Posts: 1
Re: REMAINDERS [#permalink] when three numbers are divided by 5, the remainders are 0,3 and 4 respectively. which of the following could be thr sum of the three number? Please solve this Posted from my mobile device
Tutor Joined: 17 Jul 2019 Posts: 1173 Location: Canada Schools: NYU Stern (WA) GMAT 1: 780 Q51 V45 GMAT 2: 780 Q50 V47 GMAT 3: 770 Q50 V45
Re: REMAINDERS [#permalink] If you imagine three different group of kids, maybe at summer camp, and each group is asked to arrange in mini-groups of 5 kids, group A does so with no left-over kids; group B unfortunately has 3 kids left-over (not enough to complete a group of 5); and group C unfortunately has 4 kids left-over. Now, if we combine all of the kids from group A, B, and C together and ask them to arrange in groups of 5, what will happen?The 3 and 4 left-over kids would combine to make one group of 5, and there would still be two left-over kids.Therefore, when the sum is divided by 5 the remainder is 2.Now we can infer that the correct answer must have a units digit of either 2 or 7. Only one of the answer choices will work. Sky12345 wrote: when three numbers are divided by 5, the remainders are 0,3 and 4 respectively. which of the following could be thr sum of the three number? Please solve this Posted from my mobile device _________________
Intern Joined: 17 May 2021 Posts: 5
Re: REMAINDERS [#permalink] Can someone please explain how we derive this formula - y/x=Q+r/x with an Example. Thanks in advance !
Re: REMAINDERS [#permalink] 05 Feb 2022, 10:04
Moderators:
Math Expert 10672 posts
Math Expert 87818 posts |
What is the smallest positive integer greater than 5 with remainder of 2 divided by 3,4 and 5
Pos Terkait
![What is the de Broglie wavelength of the particle with mass 1 kg that is moving at a speed of sound 430 m/s ]?](https://ap.cdnki.com/r_what-is-the-de-broglie-wavelength-of-the-particle-with-mass-1-kg-that-is-moving-at-a-speed-of-sound-430-ms----d33c23db3f66750bcaf1e16b8daf3cfd.webp)
Copyright © 2024 membukakan Inc.
