Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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 

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/   
Associated Topics:
High School Sequences, Series

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.