Задача 78267
|
|
 |
Условие
a, b, p – любые целые числа. Доказать, что найдутся такие взаимно простые k, l, что ak + bl делится на p.
Решение
Поскольку можно поменять знак у чисел k и l, можно
считать, что a ≥ 0 и b ≥ 0.
Докажем утверждение индукцией по a + b. Случай, когда a = 0 либо b = 0, очевиден.
Шаг индукции. Пусть 0 < b ≤ a. В силу предположения индукции найдутся такие взаимно простые числа m и n, что (a – b)m + bn делится на p, а значит,
am + b(n – m) делится на p. Поскольку m и n взаимно просты, то и m и n – m взаимно просты.
