Задача 35406

Темы:    [ Деление с остатком ] [ Индукция (прочее) ] [ НОД и НОК. Взаимная простота ] [ Доказательство от противного ]

Сложность: 4+ Классы: 8,9,10

Условие

Дано n целых чисел, каждое из которых взаимно просто с n. Также дано неотрицательное целое число  r < n.
Докажите, что среди данных n чисел можно выбрать несколько чисел, сумма которых дает остаток r при делении на n.

Подсказка

Доказывайте следующее более общее утверждение: если дано k  (0 < k < n + 1)  чисел, взаимно простых с n, то среди сумм некоторых из этих k чисел встретится не менее k остатков от деления на n.

Решение

  Утверждение задачи следует из более общего утверждения: если дано k  (0 < k ≥ n)  чисел, взаимно простых с n, то среди сумм некоторых из этих k чисел встретится не менее k остатков от деления на n. Последнее утверждение докажем индукцией по k. База  (k = 1)  очевидна.
  Шаг индукции. Пусть даны числа a₀, a₁, a₂, ..., a_k  (k + 1 ≤ n),  взаимно простые с n. По предположению индукции среди сумм некоторых из чисел a₁, a₂, ..., a_k встретится не менее k различных остатков от деления на n; пусть R – множество этих остатков. Если R в более k элементов, то все уже доказано. Пусть в R ровно k элементов и среди сумм некоторых из чисел a₀, a₁, a₂, ..., a_k встречаются только остатки из множества R. Рассмотрим сумму S некоторых из чисел a₁, a₂, ..., a_k, дающую остаток  r ∈ R  от деления на n. Тогда сумма  S + a₀  снова даёт некоторый остаток  r' ∈ R.  Отсюда следует, что для любого остатка  r ∈ R  остаток числа  r + a₀  также принадлежит R. Значит, остатки всех чисел  r,  r + a₀,  r + 2a₀,  ...,  r + (n – 1)a₀  принадлежат множеству R, состоящему из  k < n  остатков. Однако, выписанные числа дают различные остатки от деления на n. Действительно, разность  (r + ka₀) – (r + ma₀) = (k – m)a₀  не делится на n, так как  0 < |k – m| < n,  а  (a₀, n) = 1.  Противоречие.

Источники и прецеденты использования

web-сайт

задача