Problem 4 (3 pts): Let n be a positive integer. Show that among any group of n 1 (not necessarily consecutive) positive integers there are at least two with the same reminder when they are divided by n.

There are two integers in the group of n+1 integers with exactly the same remainder when they are divided by n.

Explanation:

Generally, if a number is divided by p(positive integer), then the possible remainders will be from 0 to p-1.

Here, the possible remainders when an integer is divided by n are 0,1,,n-1

so the number of possible remainders when an integer is divided by n is n.

In this case, the number of objects is n+1 integers and the number of boxes (remainders) is n.

p/k = (n+1)/n

= 1+(1/n)

= 2

Here, 0<1/n<1

Add 1 on both sides to get the following

0+1 < 1+1/n<1+1

1<1+1/n<2

so the value of p/k = 2 means that there is atleast one remainder which is same for two integers when they are divided by n

There are therefore two integers in the group of n+1 integers with exactly the same remainder when they are divided by n.