# Proving A Division Property By Employing The Pigeon-Hole Pricinple

• Apr 23rd 2013, 12:25 PM
Bashyboy
Proving A Division Property By Employing The Pigeon-Hole Pricinple

Here is the problem: Let $n$ be a positive integer. Show that in any set of $n$ consecutive integers there is exactly one divisible by $n$.

Here is the solution:

Let $a, a+1,...,a+n-1$ be the integers in the sequence. The integers $(a+i) \mod n$, $i=0,1,2...,n-1$, are distinct because $0< (a+j)-(a+k) whenever $0 \le k < j < n-1$. Because there are n possible values for $(a+i) \mod n$ and there are n different integers integers in the set, each of these values is taken exactly once. It follows that there is exactly one integer in the sequence that is divisible by n.

Something I don't quite understand: How does
$0< (a+j)-(a+k) make the values calculated from the modulus distinct? Also, what is the motivation
for
$0< (a+j)-(a+k)? Why are we allowed to use this fact?

• Apr 23rd 2013, 01:27 PM
HallsofIvy
Re: Proving A Division Property By Employing The Pigeon-Hole Pricinple
Quote:

Originally Posted by Bashyboy

Here is the problem: Let $n$ be a positive integer. Show that in any set of $n$ consecutive integers there is exactly one divisible by $n$.

Here is the solution:

Let $a, a+1,...,a+n-1$ be the integers in the sequence. The integers $(a+i) \mod n$, $i=0,1,2...,n-1$, are distinct because $0< (a+j)-(a+k) whenever $0 \le k < j < n-1$. Because there are n possible values for $(a+i) \mod n$ and there are n different integers integers in the set, each of these values is taken exactly once. It follows that there is exactly one integer in the sequence that is divisible by n.

Something I don't quite understand: How does
$0< (a+j)-(a+k) make the values calculated from the modulus distinct?

Since the difference of any two such number is NOT 0, they cannot be equal.
Quote:

Also, what is the motivation
for
Quote:

$0< (a+j)-(a+k)? Why are we allogerwed to use this fact?

You are told that " $0 \le k < j < n-1$".

(a+ j)- (a+ k)= j- k. It is greater than 0 because j is larger than k. It is less than n because j- k is less than j which is itself less than n.
• Apr 23rd 2013, 01:45 PM
emakarov
Re: Proving A Division Property By Employing The Pigeon-Hole Pricinple
Quote:

Originally Posted by Bashyboy
How does $0< (a+j)-(a+k) make the values calculated from the modulus distinct?

Quote:

Originally Posted by HallsofIvy
Since the difference of any two such number is NOT 0, they cannot be equal.

I would rather say the following. If j > k and (a + j) mod n = (a + k) mod n, then (a + j) - (a + k) = 0 mod n, i.e., (a + j) - (a + k) is a multiple of n. This means that either (a + j) - (a + k) = 0 or (a + j) - (a + k) ≥ n. If we exclude both of these options, this would mean that (a + j) mod n ≠ (a + k) mod n.