10-2-12
Автомат работает с магнитной карточкой, на которой может
быть записана любая пара натуральных чисел. С записью (m; n) он умеет
совершать любое из следующих действий:
1) менять числа местами: (m; n)-->(n;m) ;
2) заменять первое число суммой первого и второго: (m; n)-->(m + n; n);
3) заменять второе число модулем разности первого и второго:
(m; n)-->(m; |m - n|).
Других действий автомат выполнять не может.
Докажите, что никакие манипуляции с автоматом и карточкой, на
которой изначально записаны числа (1037;1159) , не позволят получить на
ней запись (611;1081).
- Решение
Решение
Можно заметить, что все операции, производимые автоматом,
сохраняют НОД предъявленной ему пары чисел.
Числа, представленные в условии, разлагаются на простые множители
следующим образом: 1037 = 17 ˣ 61, 1159 = 19 ˣ 61, 611 = 13 ˣ 47, 1081 = 23 ˣ 47.
Таким образом НОД первой пары равен 61, а второй – 47, и,
следовательно, вторая пара из первой получена быть не может.
- Ответ
Ответ
Что и требовалось доказать.