Три ненулевых целых числа

*

Сложность: 

Даны три ненулевых целых числа K, M и N, причём K и M взаимно просты. Докажите, что найдётся такое целое x, что Mx + N делится на K.

Подсказка

Для взаимно простых K и M существуют целые a и b такие, что Ka + Mb = −1.

Для доказательства рассмотрим остатки от деления каждого из чисел ряда M, 2M, 3M, ... на K. Поскольку K и M взаимно простые, то любые K последовательных чисел из этого ряда дают при делении на K попарно различные остатки от 0 до K − 1. (В противном случае, если бы существовало два числа mM и nM, 0 < nm < K, дающих при делении на K одинаковые остатки, то их разность делилась бы нацело на K, что невозможно, поскольку ни M, ни nm на K не делится.) Таким образом, среди любых K последовательных чисел данного ряда найдётся такое, которое даёт при делении на K остаток 1, то есть существуют целые числа c и d такие, что cM = dK + 1. Полагая a = d, b = −c, получаем требуемое равенство.

Решение

Так как K и M взаимно просты, то существуют целые a и b такие, что Ka + Mb = −1. Умножая это равенство на N, получаем

KNa + MNb = −N.

Отсюда следует, что M(Nb) + N делится на K.




Комментарии

Learning a ton from these neat arceilts.

Добавить комментарий

Plain text

  • Запрещены тэги HTML.
  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Строки и параграфы переносятся автоматически.