Задачи и олимпиады по математике

Задача

а) Пусть m₀ и m₁ – целые числа, &nbsp0 < 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 от &nbspk – 1&nbsp до 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).

Ответ

Ответ задачи отсутствует

Задача

Решение

Ответ

Подтверждение удаления