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.

This number when divided by 4 gives a remainder 3
"                         " 3 gives a remainder 2
"                         " 2 gives a remainder 1

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search