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

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

Условие

  а) Пусть m0 и m1 – целые числа,  0 < m1m0.  Докажите, что при некотором  k > 1  существуют такие целые числа a0, a1, ..., ak и m2, ..., mk, что
m1 > m2 > m3 > ... > mk > 0,  ak > 1,
  m0 = m1a0 + m2,
  m1 = m2a1 + m3,
  m2 = m3a2 + m4,
    ...
  mk–2 = mk–1ak–1 + mk,
  mk–1 = mkak,
и  (m0, m1) = mk.

  б) Докажите, что для любого s от  k – 1  до 0 существуют такие числа us, vs, что   msus + ms+1vs = d,   где  d = (m0, m1).
  В частности, для некоторых u и v выполняется равенство  m0u + m1v = d.


Решение

  а) Числа a0 и m2 получаются как частное и остаток при делении m0 на m1 числа a1 и m2 – как частное и остаток при делении m1 на m2, и так далее. Поскольку числа все время уменьшаются, процесс когда-нибудь закончится, то есть на каком-то шаге остаток будет равен нулю.

  б) Обратная индукция по k.
  База.  mk–1 = mkak = (ak – 1)mk + mk = (ak – 1)mk + d,  то есть  uk–1 = 1,  vk–1 = ak – 1.
  Шаг индукции. Пусть  d = msus + ms+1vs.  Тогда  d = msus + (ms–1msas)vs = ms–1vs + ms(us – asvs).

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

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

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

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