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

Проект МЦНМО
при участии
школы 57
Задача 60993
Темы:    [ Рекуррентные соотношения (прочее) ]
[ НОД и НОК. Взаимная простота ]
[ Алгоритм Евклида ]
Сложность: 4
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Последовательность a0, a1, a2, ... задана условиями  a0 = 0,  an+1 = P(an)  (n ≥ 0),  где P(x) – многочлен с целыми коэффициентами,  P(x) > 0  при  x ≥ 0.
Докажите, что для любых натуральных m и k  (am, ak) = a(m, k).


Решение

  Пусть Q – многочлен с целыми коэффициентами, a – целое число. Тогда  (Q(a), a) = (Q(0), a).
  Пусть  m > k.  Положим    Тогда   (am, ak) = (Q(ak), ak) = (Q(0), ak) = (am-k, ak).
  Применяя алгоритм Евклида, получаем отсюда, что  (am, ak) = a(m, k).

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

книга
Автор Алфутова Н.Б., Устинов А.В.
Год издания 2002
Название Алгебра и теория чисел
Издательство МЦНМО
Издание 1
глава
Номер 6
Название Многочлены
Тема Многочлены
параграф
Номер 2
Название Алгоритм Евклида для многочленов и теорема Безу.
Тема Теорема Безу. Разложение на множители
задача
Номер 06.070

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

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