Аддитивная комбинаторика

Заметим, что если какой-то остаток встречается раз, то мы можем взять этот остаток раз и условие будет выполнятся. Будем считать, что каждый остаток встречается меньше раз. Давайте положим в множество элементы Теперь будем последовательно заполнять множества оставшимися остатками. А именно, будем брать остаток и последовательно его класть в множества и так для каждого остатка. Заметим, что два раза мы в одно множество один и тот же остаток положить не можем, так как тогда этого остатка было бы хотя бы штук. Также заметим, что пустых множеств не будет, ведь у нас остался хотя бы элемент (в силу того, что Тогда по теореме Коши-Дэвенпорта получаем, что

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