Задача 60488

Темы:    [ НОД и НОК. Взаимная простота ] [ Алгоритм Евклида ] [ Индукция (прочее) ]

Сложность: 3+ Классы: 8,9,10 Название задачи: Алгоритм Евклида.

Условие

  а) Пусть m₀ и m₁ – целые числа,  0 < m₁ ≤ m₀.  Докажите, что при некотором  k > 1  существуют такие целые числа a₀, a₁, ..., a_k и m₂, ..., m_k, что
m₁ > m₂ > m₃ > ... > m_k > 0,  a_k > 1,
  m₀ = m₁a₀ + m₂,
  m₁ = m₂a₁ + m₃,
  m₂ = m₃a₂ + m₄,
    ...
  m_k–2 = m_k–1a_k–1 + m_k,
  m_k–1 = m_ka_k,
и  (m₀, m₁) = m_k.

  б) Докажите, что для любого s от  k – 1  до 0 существуют такие числа u_s, v_s, что   m_su_s + m_s+1v_s = d,   где  d = (m₀, m₁).
  В частности, для некоторых u и v выполняется равенство  m₀u + m₁v = d.

Решение

  а) Числа a₀ и m₂ получаются как частное и остаток при делении m₀ на m₁ числа a₁ и m₂ – как частное и остаток при делении m₁ на m₂, и так далее. Поскольку числа все время уменьшаются, процесс когда-нибудь закончится, то есть на каком-то шаге остаток будет равен нулю.

  б) Обратная индукция по k.
  База.  m_k–1 = m_ka_k = (a_k – 1)m_k + m_k = (a_k – 1)m_k + d,  то есть  u_k–1 = 1,  v_k–1 = a_k – 1.
  Шаг индукции. Пусть  d = m_su_s + m_s+1v_s.  Тогда  d = m_su_s + (m_s–1 – m_sa_s)v_s = m_s–1v_s + m_s(u_s – a_sv_s).

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

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