Podzielmy wszystkie liczby naturalne na \(n\) klas reszt modulo \(n\): \[ C_0, C_1, \dots, C_{n-1}, \] gdzie \[ C_k = \{\,m\in\mathbb{N}:m\equiv k\pmod n\},\quad k=0,1,\dots,n-1. \] Każda liczba zadanego zbioru należy więc do jednej z tych \(n\) klas.

Mamy \(n+1\) liczb i tylko \(n\) klas. Z zasady Dirichleta wynika, że co najmniej w jednej klasie znajdą się dwie liczby, powiedzmy \(a\) i \(b\). Wówczas \[ a\equiv b\pmod n \quad\Longrightarrow\quad a - b \equiv 0\pmod n, \] czyli \(n\) dzieli różnicę \(a-b\).

Stąd w dowolnym zbiorze \(n+1\) liczb naturalnych zawsze znajdą się dwie, których różnica jest podzielna przez \(n\).