Course contentsShow
← Mathematics
Lesson 2573 of 3,12151. Discrete Math — Sets, Relations, FunctionsFree lesson

Pigeonhole Principle in Number Theory

Using the principle to prove results about divisibility, remainders, and modular arithmetic.

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:

  1. Identify how many distinct remainders exist (these are your pigeonholes)
  2. Count how many integers you have (these are your pigeons)
  3. Apply the Pigeonhole Principle to guarantee a collision
  4. 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.