Решение задачи 304

Условие:

Имеются три автомата. Получив пару чисел (n,m), первый из них преобразует ее в пару (n,m), второй преобразует в пару (m,n−m), третий -- в пару (m,n+m). Можно ли преобразовать пару (19,86) в пару (12,21)?

Решение:

Заметим, что НОД пары чисел не меняется. Действительно, пусть a,b -- натуральные числа и a>b, обозначим через (a,b) их НОД. Тогда (a,b)=(a-b,b)=(a+b,b). Подробнее можно почитать здесь. НОД чисел 19 и 86 равен 1, а НОД чисел 12 и 21 равен 3, следовательно преобразовать пару (19,86) в пару (12,21) нельзя.

Ответ: Нет.