, 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}$.