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.