Second Round of the 73rd Czech and Slovak Mathematical Olympiad (January 16th, ), 2024

We shall prove that every pair $(k, n)$ works.

First, if $n = 1$, we can just take $(a, b) = (k, k)$, then
$$\text{gcd}(a + k, b) = \text{gcd}(2k, k) = k = \text{gcd}(k, k) = \text{gcd}(a, b).$$

Now, assume that $n > 1$, then $nk - k > 0$ is a natural number and we can take $(a, b) = ((n-1)k, nk)$. Then we clearly have:
$$\text{gcd}(a + k, b) = \text{gcd}((n-1)k + k, nk) = \text{gcd}(nk, nk) = nk,$$
$$\text{gcd}(a, b) = \text{gcd}((n-1)k, nk) = k,$$
so
$$\text{gcd}(a + k, b) = n \cdot \text{gcd}(a, b).$$
Therefore, every pair $(k, n)$ works.