Номер 28.23, страница 235 - гдз по алгебре 8 класс учебник Мерзляк, Поляков

Глава 5. Основы теории делимости. Параграф 28. Наибольший общий делитель и наименьшее общее кратное двух натуральных чисел. Взаимно простые числа - номер 28.23, страница 235.

Условие.

28.23. Три автомата печатают на карточках пары целых чисел. Каждый автомат, прочитав некоторую карточку, выдаёт новую карточку. Прочитав карточку с парой чисел $(m; n)$, первый автомат выдаёт карточку с числами $(m - n; n)$, второй — карточку с числами $(m + n; n)$, третий — карточку с числами $(n; m)$. Сначала есть карточка с парой чисел $(46; 51)$. Можно ли, используя автоматы в некотором порядке, получить карточку с парой чисел $(15; 33)$?

Решение.

Проанализируем операции, которые выполняют автоматы над парой чисел $(m; n)$:

1. Первый автомат: $(m; n) \rightarrow (m - n; n)$

2. Второй автомат: $(m; n) \rightarrow (m + n; n)$

3. Третий автомат: $(m; n) \rightarrow (n; m)$

Чтобы определить, можно ли из одной пары чисел получить другую, поищем инвариант — величину, которая не изменяется при выполнении указанных операций. В данном случае таким инвариантом является наибольший общий делитель (НОД) пары чисел.

Проверим, что НОД сохраняется при каждой операции:

1. Для первого и второго автоматов используется свойство наибольшего общего делителя: $\text{НОД}(a, b) = \text{НОД}(a \pm b, b)$. Таким образом, $\text{НОД}(m, n) = \text{НОД}(m-n, n)$ и $\text{НОД}(m, n) = \text{НОД}(m+n, n)$. НОД сохраняется.

2. Для третьего автомата, который меняет числа местами, очевидно, что $\text{НОД}(m, n) = \text{НОД}(n, m)$. НОД также сохраняется.

Поскольку каждая из трех операций сохраняет НОД пары чисел, любая последовательность этих операций также будет сохранять НОД исходной пары.

Теперь вычислим НОД для начальной и конечной пар чисел.

Для начальной пары $(46; 51)$:
Разложим числа на простые множители:
$46 = 2 \times 23$
$51 = 3 \times 17$
У чисел 46 и 51 нет общих простых делителей, следовательно, $\text{НОД}(46, 51) = 1$.

Для целевой пары $(15; 33)$:
Разложим числа на простые множители:
$15 = 3 \times 5$
$33 = 3 \times 11$
Наибольший общий делитель этих чисел равен 3, то есть $\text{НОД}(15, 33) = 3$.

Так как НОД начальной пары ($\text{НОД}(46, 51) = 1$) не равен НОД целевой пары ($\text{НОД}(15, 33) = 3$), а НОД является инвариантом для всех допустимых операций, то из пары $(46; 51)$ невозможно получить пару $(15; 33)$.

Ответ: нет, нельзя.