# Fun with counting and modular arithmetic

1. Jul 16, 2007

### Chromium

So today I was doing a problem out of my book for practice, and I came across some interesting results.

Show that among any group of five (not necessarily consecutive) integers, there are two with the same remainder when divided by 4.

a set of consecutive integers

1 mod 4 = 1
2 mod 4 = 2
3 mod 4 = 3
4 mod 4 = 0
5 mod 4 = 1

a set of nonconsecutive integers

6 mod 4 = 2
14 mod 4 = 2
3 mod 4 = 3
71 mod 4 = 3
35 mod 4 = 3

should the question be rephrased like this?
Show that among any group of five (not necessarily consecutive) integers, there are two or more with the same remainder when divided by 4.

2. Jul 17, 2007

### Dick

"There are two" is an informal (if inexact) way of expressing "there are two or more". I.e. if there are two or more, then there ARE certainly two that are equal. Shouldn't you be solving the problem, not doing linguistic hair splitting? Or is this a linguistics class? :)

Last edited: Jul 17, 2007
3. Jul 17, 2007

### ZioX

This is a simple pigeonhole problem. What are the pigeons and what are the holes? I assume you are familiar with the pigeonhole theorem.

In determining the holes, you'll want to consider the division algorithm.