Три ненулевых целых числа
*
Даны три ненулевых целых числа K, M и N, причём K и M взаимно просты. Докажите, что найдётся такое целое x, что Mx + N делится на K.
Для взаимно простых K и M существуют целые a и b такие, что
Для доказательства рассмотрим остатки от деления каждого из чисел ряда M, 2M, 3M, ... на K. Поскольку K и M взаимно простые, то любые K последовательных чисел из этого ряда дают при делении на K попарно различные остатки от 0 до
Так как K и M взаимно просты, то существуют целые a и b такие, что
KNa + MNb = −N.
Отсюда следует, что M(Nb) + N делится на K.
Комментарии
Learning a ton from these neat arceilts.
Добавить комментарий