example of pigeonhole principle

A example.

Theorem.

For any set of $\mathrm{8}$ integers, there exist at least two of them whose difference is divisible by $\mathrm{7}$.

Proof.

The residue classes modulo $7$ are $0,1,2,3,4,5,6$. We have seven and eight integers. So it must be the case that 2 integers fall on the same residue class, and therefore their difference will be divisible by $7$. ∎

Title	example of pigeonhole principle
Canonical name	ExampleOfPigeonholePrinciple
Date of creation	2013-03-22 12:41:32
Last modified on	2013-03-22 12:41:32
Owner	Mathprof (13753)
Last modified by	Mathprof (13753)
Numerical id	8
Author	Mathprof (13753)
Entry type	Example
Classification	msc 05-00