Каталог по темам

Задачи

Страница: << 7 8 9 10 11 12 13 >> [Всего задач: 277]

Задача 60487

Тема:

[

НОД и НОК. Взаимная простота

]

Сложность: 3+
Классы: 8,9,10

В задаче 60274 доказана возможность деления с остатком произвольного целого числа a на натуральное число b.
Докажите, что из равенства a = bq + r следует соотношение (a, b) = (b, r).

Прислать комментарий

Решение

Задача 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.