Для каждого остатка оценим сверху количество таких в для которых этот остаток есть среди чисел Сначала заметим, что сравнимо с ровно при одном от до И пусть при этом единственном число сравнимо с по модулю То есть каждой паре соответствует единственный остаток

Рассмотрим фиксированный остаток Предположим, что не делится на Пусть он встречается ровно раз. Обозначим через количества чисел (среди ), которые равны по модулю на шагах, где встречается хотя бы один раз остаток Тогда так как любой такой остаток будет встречаться раз в сумме для всех (по одному разу за каждый кроме ). А количество пар, которым соответствует остаток равно

Обозначим его через С другой стороны

Если же делится на то То есть в этом случае

Теперь просуммируем по всем остаткам по модулю Получим, что сумма количеств различных остатков среди по всем от до не меньше, чем

Тогда при каком-то количество различных остатков не меньше, чем

что и требовалось.