Каталог по источникам

Задачи

Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 45]

Задача 60488 (#3.36-3.37)

[Алгоритм Евклида]

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

Сложность: 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.

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

Решение

Задача 60489 (#03.037)

Темы:	[	НОД и НОК. Взаимная простота	]
	[	Принцип Дирихле (прочее)	]
	[	Принцип крайнего (прочее)	]
	[	Геометрические интерпретации в алгебре	]
	[	Уравнения в целых числах	]

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

a, b, c – целые числа; a и b отличны от нуля.
Докажите, что уравнение ax + by = c имеет решения в целых числах тогда и только тогда, когда c делится на d = НОД(a, b).