ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 78267
Темы:    [ Арифметика остатков (прочее) ]
[ Индукция (прочее) ]
[ НОД и НОК. Взаимная простота ]
Сложность: 3+
Классы: 8,9
В корзину
Прислать комментарий

Условие

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  взаимно просты.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 24
Год 1961
вариант
1
Класс 9
Тур 2
задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .