A pair of integers are written on a blackboard. At each step, we are allowed to erase the pair of numbers $(a, b)$ from the board and replace it with one of the following pairs: $(b, a), (a − b, b), (a + b, b)$. If we start with $(2022, 315)$ written on the blackboard, then can we eventually have the pair
(a) $(30, 45)$,
(b) $(222, 15)$?
Note that $\gcd(2022,315) = 3$, $\gcd(30,45) = 15$ and $\gcd(222,15) = 3$.
By Bezout's identity, any number which is a multiple of $3$ can be written in the form $2022x+315y$ for some integers $x$ and $y$.
Note that each of the numbers $30,45,222,15$ are divisible by $3$.
Can anyone provide some hints on how to proceed?
Source: Homework Assignment problems.
Best Answer
From the hints provided in the comments above, I will try to write a solution.
Since $\gcd (30,45) \neq \gcd(2022,315)$, the pair $(30,45)$ cannot be obtained using the given operations.
Next,
$(2022,315) \to (132,315) \to (315,132) \to (132,51) \to (51,30) \to (30,21) \to (21,9) \to (9,3)$
$ \to (12,3) \to (15,12) \to (12,15) \to (222,15).$
Hence we can reach the pair $(222,15)$ from $(2022,315)$ using the given operations.