Argentine National Olympiad 2016

The maximum value of $d_{a,b}$ equals $n^2-1$.

Let $a$ and $b$ be relatively prime. Since $d_{a,b}$ divides $na+b$ and $a+nb$, it also divides the numbers $u=(n+1)(a+b)=(na+b)+(a+nb)$ and $v=(n-1)(a-b)=(na+b)-(a+nb)$. Hence $d_{a,b}$ divides $(n-1)u+(n+1)v=2(n^2-1)a$ and $(n-1)u-(n+1)v=2(n^2-1)b$. Therefore $d_{a,b}$ divides the greatest common divisor of $2(n^2-1)a$ and $2(n^2-1)b$, which equals $2(n^2-1)$, because $a$ and $b$ are relatively prime.

Now we show that $d_{a,b}=2(n^2-1)$ is impossible. Otherwise $na+b=2(n^2-1)k$, $a+nb=2(n^2-1)l$, where $k$ and $l$ are relatively prime. These equalities form a linear system with unknowns $a$ and $b$ whose unique solution is $a=2(nk-l)$, $b=2(nl-k)$. However, the obtained values of $a$ and $b$ are even, so they are not relatively prime.

In conclusion, $d_{a,b}$ is a proper divisor of $2(n^2-1)$, hence $d_{a,b}\le n^2-1$. To see that $d_{a,b}=n^2-1$ is attainable, set $a=n(n-1)-1$, $b=1$. Then $na+b=(n-1)(n^2-1)$, $a+nb=n^2-1$. So $d_{a,b}=n^2-1$, as $n-1$ and $1$ are relatively prime. Thus $n^2-1$ is the maximum value of $d_{a,b}$.