Skip to main content
AMC 10 & 12

Pigeonhole in Number Theory

Remainders naturally sort into a small, fixed number of classes — which makes them the most common 'holes' in number theory pigeonhole arguments.

The pigeonhole principle appears constantly in number theory because remainders mod mmonly ever take mm possible values — an automatic, ready-made set of holes for any sufficiently large collection of integers.

Subset sums divisible by n

A classic application: among any nn integers, some nonempty subset of consecutiveterms in their running sum has a sum divisible by nn. The trick is to look at thenn partial sums S1,S2,…,SnS_1, S_2, \ldots, S_n (where SkS_k is the sum of the first kk terms). If any Sk≡0(modn)S_k \equiv 0 \pmod n, you’re done. Otherwise, allnn partial sums fall into only n−1n-1 nonzero residue classes mod nn — by pigeonhole, two of them share a residue, and the terms between them sum to a multiple ofnn.

Residues among a set of integers

Whenever you have more integers than the modulus you’re working with, two of them are guaranteed to share a residue — and their difference is then guaranteed divisible by that modulus. This single observation is the seed of a large number of number-theory pigeonhole problems.

Worked example

Problem: Prove that among any 6 integers, some nonempty subset has a sum divisible by 6.

Solution: Let the integers be a1,…,a6a_1, \ldots, a_6, and form the 6 partial sums S1=a1, S2=a1+a2, …, S6=a1+⋯+a6S_1=a_1,\ S_2=a_1+a_2,\ \ldots,\ S_6=a_1+\cdots+a_6. If any Sk≡0(mod6)S_k \equiv 0 \pmod 6, that prefix is our subset. Otherwise, each of the 6 partial sums has a residue in{1,2,3,4,5}\{1,2,3,4,5\} — only 5 possible nonzero values for 6 sums. By pigeonhole, two partial sums Si,SjS_i, S_j (say i<ji<j) share a residue, so Sj−SiS_j - S_i is divisible by 6. That difference is exactly ai+1+⋯+aja_{i+1}+\cdots+a_j — our subset.

Practice problems

1.Show that among any 3 integers, two of them have a sum that is even.

2.Show that among any 11 integers, two of them have a difference divisible by 10.

3.Given 7 distinct integers, show that some two of them differ by a multiple of 6, or explain why the numbers 1 through 6 (exactly 6 integers) might avoid this.

4.Prove that among any 5 integers, some nonempty subset has a sum divisible by 5.

Invariants & Parity