Rozważmy  liczb . Żadna z nich nie dzieli się przez  , więc możliwe reszty z dzielenia tych liczb przez  to . Jest ich o jeden mniej niż liczb, więc istnieją dwie liczby, powiedzmy  i  , dla , które dają tę samą resztę z dzielenia przez  . Oznacza to, że dzieli . Ale  i  są względnie pierwsze, więc dzieli . Zatem spełnia warunki zadania.