Pattern of Remainders
Date: 7/10/96 at 18:14:30 From: Anonymous Subject: Pattern of Remainders A number divided by 2 gives a remainder of 1, and when divided by 3 gives a remainder 2. Answer: 5 This number when divided by 4 gives a remainder 3 " " 3 gives a remainder 2 " " 2 gives a remainder 1 Answer: 11 The problem continues with the remainder being one less than the number it was divided by. I know there is a pattern and I've tried adding, multiplying and dividing the numbers. Help would be very much appreciated.
Date: 7/10/96 at 21:32:7 From: Doctor Pete Subject: Re: Pattern of Remainders Think of the related question, "What is the smallest number n(k) for which 2, 3, 4, ..., k divides n(k)?" For example, 60 is the smallest number for which 2, 3, 4, and 5 are divisors. Note also that 6 also divides 60. So here is a short table n(k) for different values of k: k: 2 3 4 5 6 7 8 9 10 n(k): 2 6 12 60 60 420 840 2520 2520 Notice that n doesn't follow a simple rule. Now, what does this have to do with your original question? Well, since 2, 3, 4, ..., k divides n(k), n(k)-1 will have remainders of k-1 when divided by k. Since we asked that n(k) be the smallest such number with the above property, it follows that n(k)-1 will be the smallest number which, upon dividing by 2, 3, 4, etc., will leave remainders of 1, 2, 3, etc. So the final question to be asked is, "How do you calculate n(k)?" Well, look at the case where k=4. Note it's not 24, but 12; this is because we already had 2 as a factor in n(3), so we only needed to multiply n(3) by 2 to get a factor of 4 in n(4). Similarly, n(5)= n(6)=60, since 6=2*3. So intuitively we will see that the prime factorization of n(k-1) and k will play an important role. But off the top of my head, I don't see an immediate formula to calculate these. I'll follow this up if I find one. -Doctor Pete, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum