Дано n целых чисел, каждое из которых взаимно просто с n. Также дано неотрицательное целое число  r < n. 
Докажите, что среди данных n чисел можно выбрать несколько чисел, сумма которых дает остаток r при делении на n. 
   Утверждение задачи следует из более общего утверждения: если дано k  (0 < k ≥ n)  чисел, взаимно простых с n, то среди сумм некоторых из этих k чисел встретится не менее k остатков от деления на n. Последнее утверждение докажем индукцией по k. База  (k = 1)  очевидна. 
   Шаг индукции. Пусть даны числа a0, a1, a2, ..., ak  (k + 1 ≤ n),  взаимно простые с n. По предположению индукции среди сумм некоторых из чисел a1, a2, ..., ak встретится не менее k различных остатков от деления на n; пусть R – множество этих остатков. Если R в более k элементов, то все уже доказано. Пусть в R ровно k элементов и среди сумм некоторых из чисел a0, a1, a2, ..., ak встречаются только остатки из множества R. Рассмотрим сумму S некоторых из чисел a1, a2, ..., ak, дающую остаток  r ∈ R  от деления на n. Тогда сумма  S + a0  снова даёт некоторый остаток  r' ∈ R.  Отсюда следует, что для любого остатка  r ∈ R  остаток числа  r + a0  также принадлежит R. Значит, остатки всех чисел  r,  r + a0,  r + 2a0,  ...,  r + (n – 1)a0  принадлежат множеству R, состоящему из  k < n  остатков. Однако, выписанные числа дают различные остатки от деления на n. Действительно, разность  (r + ka0) – (r + ma0) = (k – m)a0  не делится на n, так как  0 < |k – m| < n,  а  (a0, n) = 1.  Противоречие. 
Деление с остатком Индукция (прочее) НОД и НОК. Взаимная простота Доказательство от противного