Pigeonhole Principle in Number Theory
You'll learn how to apply the Pigeonhole Principle to prove surprising results about divisibility, remainders, and modular arithmetic.
The Core Idea
The Pigeonhole Principle becomes a powerful tool in number theory when we recognize that integers can be grouped by their remainders (also called residues). When we divide any integer by n, there are exactly n possible remainders: 0, 1, 2, ..., n-1. These remainders act as "pigeonholes."
If you have more than n integers, at least two must share the same remainder when divided by n. The difference between these two integers is then divisible by n—giving us divisibility results almost magically!
A Classic Example
Claim: Among any 5 integers, at least two have a difference divisible by 4.
Proof: When dividing by 4, the possible remainders are {0, 1, 2, 3}—that's 4 pigeonholes. With 5 integers (pigeons), at least two must share the same remainder by the Pigeonhole Principle. If integers a and b both have remainder r when divided by 4, then:
- a ≡ r (mod 4)
- b ≡ r (mod 4)
Therefore a - b ≡ 0 (mod 4), meaning 4 divides (a - b).
The Pattern
The typical strategy:
- Identify how many distinct remainders exist (these are your pigeonholes)
- Count how many integers you have (these are your pigeons)
- Apply the Pigeonhole Principle to guarantee a collision
- Use the collision to derive the divisibility or modular arithmetic result
Key Takeaway: The Pigeonhole Principle transforms modular arithmetic into a counting argument—if you have more integers than possible remainders, divisibility patterns must emerge.