|
|
 |
Условие
На доске написано n натуральных чисел. За одну операцию вместо двух чисел, не делящих друг друга, можно написать их наибольший общий делитель и их наименьшее общее кратное.
а) Докажите, что можно провести только конечное число операций.
б) Финальный результат независимо от порядка действий будет одним
и тем же. Например:
(4, 6, 9) → (2, 12, 9) → (2, 3, 36) → (1, 6, 36),
(4, 6, 9) → (4, 3, 18) → (1, 12, 18) → (1, 6, 36).
Решение
а) Назовём пару чисел правильной, если одно из них делится на другое. заметим, что при каждой операции число правильных пар увеличивается. Когда все пары станут правильными, процесс прекратится.
б) Пусть a1, ..., an – исходные числа. Нетрудно проверить, что при указанной операции ни одно из чисел b1 = (a1, ..., an),
b2 = ([a1, a2], [a1, a3], ..., [an–1, an]), b3 = ([a1, a2, a3], [a1, a2, a4], ..., [an–2, an–1, an]), ..., bn = [a1, a2, ..., an] не меняется.
Пусть в конце получились числа A1 ≤ ... ≤ An. Согласно а) каждое из этих чисел делится на предыдущее. Но тогда соответствующие числа B1 = b1, ..., bn = Bn совпадают с A1, ..., An.
Источники и прецеденты использования
| книга | |
| Автор | Алфутова Н.Б., Устинов А.В. |
| Год издания | 2002 |
| Название | Алгебра и теория чисел |
| Издательство | МЦНМО |
| Издание | 1 |
| глава | |
| Номер | 3 |
| Название | Алгоритм Евклида и основная теорема арифметики |
| Тема | Алгебра и арифметика |
| параграф | |
| Номер | 2 |
| Название | Алгоритм Евклида |
| Тема | Алгоритм Евклида |
| задача | |
| Номер | 03.070 |
