IMO Shortlist, 2007

The statement follows from the following fact.

Lemma. For arbitrary positive integers $x$ and $y$, the number $4 x y-1$ divides $\left(4 x^{2}-1\right)^{2}$ if and only if $x=y$.

Proof. If $x=y$ then $4 x y-1=4 x^{2}-1$ obviously divides $\left(4 x^{2}-1\right)^{2}$ so it is sufficient to consider the opposite direction.

Call a pair $(x, y)$ of positive integers bad if $4 x y-1$ divides $\left(4 x^{2}-1\right)^{2}$ but $x \neq y$. In order to prove that bad pairs do not exist, we present two properties of them which provide an infinite descent.

Property (i). If $(x, y)$ is a bad pair and $x<y$ then there exists a positive integer $z<x$ such that $(x, z)$ is also bad.

Let $r=\frac{\left(4 x^{2}-1\right)^{2}}{4 x y-1}$. Then
$$r=-r \cdot(-1) \equiv -r(4 x y-1) = -\left(4 x^{2}-1\right)^{2} \equiv -1 \quad (\bmod 4 x)$$
and $r=4 x z-1$ with some positive integer $z$. From $x<y$ we obtain that
$$4 x z-1=\frac{\left(4 x^{2}-1\right)^{2}}{4 x y-1}<4 x^{2}-1$$
and therefore $z<x$. By the construction, the number $4 x z-1$ is a divisor of $\left(4 x^{2}-1\right)^{2}$ so $(x, z)$ is a bad pair.

Property (ii). If $(x, y)$ is a bad pair then $(y, x)$ is also bad.

Since $1=1^{2} \equiv (4 x y)^{2} (\bmod 4 x y-1)$, we have
$$\left(4 y^{2}-1\right)^{2} \equiv \left(4 y^{2}-(4 x y)^{2}\right)^{2}=16 y^{4}\left(4 x^{2}-1\right)^{2} \equiv 0 \quad (\bmod 4 x y-1)$$
Hence, the number $4 x y-1$ divides $\left(4 y^{2}-1\right)^{2}$ as well.

Now suppose that there exists at least one bad pair. Take a bad pair $(x, y)$ such that $2 x+y$ attains its smallest possible value. If $x<y$ then property (i) provides a bad pair $(x, z)$ with $z<y$ and thus $2 x+z<2 x+y$. Otherwise, if $y<x$, property (ii) yields that pair $(y, x)$ is also bad while $2 y+x<2 x+y$. Both cases contradict the assumption that $2 x+y$ is minimal; the Lemma is proved.

To prove the problem statement, apply the Lemma for $x=k$ and $y=2 n$; the number $8 k n-1$ divides $\left(4 k^{2}-1\right)^{2}$ if and only if $k=2 n$. Hence, there is no such $n$ if $k$ is odd and $n=k / 2$ is the only solution if $k$ is even.