Выбор модуля для доказательства делимости / простоты / степени

Рассмотрим числа Предположим, что среди них нет ни одного, кратного Следовательно, среди них найдутся два различных числа и дающих один и тот же остаток при делении на поскольку всего остатков и остаток среди чисел не встречается. То есть Таким образом, (не умаляя общности Нетрудно видеть, не имеет общих делителей с Значит, делится на Но это число принадлежит набору и мы предположили, что ни одно из этих чисел не кратно пришли к противоречию.