China Hong Kong Mathematical Olympiad

a. Yes. Since $s, t \neq 0$, $s^2 + t^2 \geq 2$. Let $p$ be any prime divisor of $s^2 + t^2$. If $p \mid t$, then $p \mid s$, and so $\gcd(s, t) \geq p$. This shows $(s, t)$ is good. If $p \nmid t$, then there exists $k \in \mathbb{Z}^+$ such that $tk \equiv -s \pmod{p}$. Then we have $p \mid s + kt$. Also, we have
$$t - ks = t - (-t^{-1}s)s = t^{-1}(t^2 + s^2) \equiv 0 \pmod{p}.$$
Thus, $\gcd(s+kt, t-ks) \geq p$. This shows $(s, t)$ is a good pair as we can apply $k$ moves to $(s, t)$ to obtain $(s + kt, t - ks)$.

b. Let $\gcd(s, t) = d$. By Bézout's identity, there exist $m, n \in \mathbb{Z}$ such that $ms + nt = d$. We claim that the pair $(m, n)$ is not good.
After $k$ moves, the pair becomes $(m + kt, n - ks)$. If there exists a prime $p$ dividing both $m + kt$ and $n - ks$, then
$$p \mid (m + kt) \frac{s}{d} + (n - ks) \frac{t}{d} = \frac{ms + nt}{d} = 1.$$
This is impossible. Therefore, $\gcd(m + kt, n - ks) = 1$ for any $k$. This proves our claim.