Eratosthenes via pigeonhole

#pigeonhole#primes#sieve

Statement

Show that among any $n+1$ primes, some two differ by a multiple of $n$ .

Hint

Residues mod $n$ .

Show solutionHide solution

Residues. Primes have residues in $\{0,1,\ldots,n-1\}$ (n values).

Pigeonhole. $n+1$ primes, $n$ residues: two share a residue.

Conclusion. Their difference is divisible by $n$ .