, 2015

We will proceed by steps.

- First Step: We prove it for $n = p$ a prime number, with $p \geq 7$:

If $p$ divides $k$ then $a = b = 1$ satisfy the condition. If $p$ does not divide $k$ then let us consider two cases:

a. If $k$ is a quadratic residue modulo $p$, and $c$ and $c+1$ are two consecutive quadratic residues modulo $p$ such that $1 \leq c < c+1 \leq p-1$, then both $k c$ and $k c + k$ are quadratic residues relatively prime with $p$. This means that there exist $a$ and $b$, each relatively prime with $p$, such that $a^{2} \equiv c k$ and $b^{2} \equiv c k + k$ modulo $p$ and therefore $a^{2} - b^{2} + k \equiv 0 \pmod{p}$.

b. If $k$ is a quadratic nonresidue modulo $p$, and $c$ and $c+1$ are two consecutive quadratic nonresidues modulo $p$ such that $1 \leq c < c+1 \leq p-1$, then both $k c$ and $k c + k$ are quadratic residues relatively prime with $p$. This means that there exist $a$ and $b$, each relatively prime with $p$, such that $a^{2} \equiv c k$ and $b^{2} \equiv c k + k$ modulo $p$ and therefore $a^{2} - b^{2} + k \equiv 0 \pmod{p}$.

Thus, this first step reduces to proving that among $1, 2, \ldots, p-1$ there are two consecutive quadratic residues and two consecutive quadratic nonresidues modulo $p$. We will prove this fact in two different ways:

First way. Notice that both $1$ and $4$ are quadratic residues.
If $2$ or $3$ is a quadratic residue then there exists at least two consecutive quadratic residues among $1, 2, 3, 4$. But exactly half of the numbers $1, 2, \ldots, p-1$ are quadratic nonresidues. So there exist at least $\frac{p-3}{2}$ quadratic nonresidues among the $p-5$ consecutive numbers $5, 6, \ldots, p-1$. So, by a pigeonhole principle, at least two of them must be consecutive.
If $2$ and $3$ are consecutive quadratic nonresidues, we have two possibilities: Either $-1$ is a quadratic nonresidue and in this case $p-3$ and $p-2$ are consecutive quadratic residues, or $-1$ is a quadratic residue, which means that $p \equiv 1 \pmod{4}$, $p \geq 13$, and for each integer $m$ the integers $m$ and $p-m$ are either both quadratic residues or both quadratic nonresidues. This means that there are $\frac{p-1}{4}$ quadratic residues between $1, 2, \ldots, \frac{p-1}{2}$.
If $\frac{p-1}{2}$ is a quadratic residue then $\frac{p-1}{2}, \frac{p+1}{2}$ are two consecutive quadratic residues.
If $\frac{p-1}{2}$ is a quadratic nonresidue then there are $\frac{p-5}{4}$ quadratic residues among the $\frac{p-9}{2}$ consecutive numbers $4, 5, \ldots, \frac{p-3}{2}$. But $\frac{p-9}{2}$ is an even number. So, by a pigeonhole principle, at least two of the quadratic residues must be consecutive.

Second way. In this second way we will compute the exact number of consecutive pairs of quadratic residues and the exact number of consecutive pairs of quadratic nonresidues.
Consider the partition
$$\{1, 2, \ldots, p-1\} = Q_{1} \cup N_{1} \cup Q_{2} \cup N_{2} \cup \cdots \cup Q_{k} \cup N_{k}$$
where $Q_{1}$ is the set of all the first consecutive quadratic residues, possibly reduced to the singleton $\{1\}$ when $2$ is a quadratic nonresidue, $N_{1}$ is the set of all the first consecutive quadratic nonresidues, possibly reduced to a singleton, $Q_{2}$ is the set of all the first consecutive quadratic residues after the elements of $N_{1}$, and so on... Notice that $N_{k}$ is the only possibly empty set when $p-1$ is a quadratic residue.
Let $a \in \{1, 2, \ldots, p-2\}$. Notice that $\left(\frac{a}{p}\right)\left(\frac{a+1}{p}\right) = 1$ if and only if $a, a+1$ are both quadratic residues or both quadratic nonresidues, where $\left(\frac{a}{p}\right)$ is the Legendre symbol. This means that $\left(\frac{a}{p}\right)\left(\frac{a+1}{p}\right) = -1$ if and only if $a, a+1$ do not belong to the same subset of the partition. This means that there are either $2k-2$ or $2k-1$ pairs $(a, a+1)$, with $1 \leq a \leq p-2$ such that $\left(\frac{a}{p}\right)\left(\frac{a+1}{p}\right) = -1$, depending on whether $N_{k}$ is empty or not. But $\left(\frac{a}{p}\right)\left(\frac{a+1}{p}\right) = \left(\frac{a}{p}\right)^{2}\left(\frac{1+a^{-1}}{p}\right) = \left(\frac{1+a^{-1}}{p}\right)$. But when $a$ covers all the residues $1, 2, \ldots, p-2$, its inverse $a^{-1}$ covers all the residues $1, 2, \ldots, p-2$. Because there are exactly $\frac{p-1}{2}$ quadratic nonresidues among the residues $2, 3, \ldots, p-1$, we deduce that $k = \frac{p+3}{4}$ if $p \equiv 1 \pmod{4}$ and $k = \frac{p+1}{4}$ if $p \equiv 3 \pmod{4}$.
Now, for $1 \leq i \leq k$, there are $\operatorname{Card} Q_{i} - 1$ consecutive pairs of quadratic residues in $Q_{i}$ and $\operatorname{Card} N_{i} - 1$ consecutive pairs of quadratic nonresidues in $N_{i}$. We deduce that the total number of consecutive pairs of quadratic residues in $\{1, 2, \ldots, p-1\}$ is
$$\sum_{i=1}^{k} (\operatorname{Card} Q_{i} - 1) = \operatorname{Card} \bigcup_{i=1}^{k} Q_{i} - k = \frac{p-1}{2} - k = \left\lfloor \frac{p-3}{4} \right\rfloor \geq 1,$$
and the total number of consecutive pairs of quadratic nonresidues in $\{1, 2, \ldots, p-1\}$ is
$\sum_{i=1}^{k-1} (\operatorname{Card} N_{i} - 1) = \operatorname{Card} \bigcup_{i=1}^{k-1} N_{i} - k + 1 = \frac{p-1}{2} - k + 1 = \left\lfloor \frac{p-1}{4} \right\rfloor \geq 1$, if $p \equiv 1 \pmod{4}$ and
$$\sum_{i=1}^{k} (\operatorname{Card} N_{i} - 1) = \operatorname{Card} \bigcup_{i=1}^{k} N_{i} - k = \frac{p-1}{2} - k = \left\lfloor \frac{p-1}{4} \right\rfloor \geq 1,$$
if $p \equiv 3 \pmod{4}$.

- Second Step: We prove it for $n = p^{\alpha}$, with $p \geq 7$ is a prime number and $\alpha \geq 1$. We proceed by induction on $\alpha$:

For $\alpha = 1$, we have already proved in the first step that there exist two integers $a_{1}, b_{1}$, each relatively prime with $p$, such that $p$ divides $a_{1}^{2} - b_{1}^{2} + k$.
For $\alpha \geq 1$, assume that there exists an integer $a_{\alpha} \equiv a_{1} \pmod{p}$ such that $p^{\alpha}$ divides $a_{\alpha}^{2} - b_{1}^{2} + k$. Consider the polynomial $P(X) = X^{2} - b_{1}^{2} + k$. Because $P(a_{\alpha}) \equiv 0 \pmod{p^{\alpha}}$ and $P'(a_{\alpha}) = 2 a_{\alpha} \equiv 2 a_{1} \not\equiv 0 \pmod{p}$, there exists, from Hensel's lemma, an integer $a_{\alpha+1} \equiv a_{\alpha} \pmod{p^{\alpha}}$, and therefore $a_{\alpha+1} \equiv a_{1} \pmod{p}$, such that $P(a_{\alpha+1}) = a_{\alpha+1}^{2} - b_{1}^{2} + k \equiv 0 \pmod{p^{\alpha+1}}$. This proves the induction.

- Last Step: We prove the general case when $n = p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p_{l}^{\alpha_{l}}$, where $7 \leq p_{1} < p_{2} < \cdots < p_{l}$ are prime numbers. We know from the second step, that for each $i = 1, 2, \ldots, l$, there exist two integers $a_{i}, b_{i}$, relatively prime with $p_{i}$, such that $p_{i}^{\alpha_{i}}$ divides $a_{i}^{2} - b_{i}^{2} + k$. From the Chinese remainder theorem, there exist two integers $a, b$ such that $a \equiv a_{i} \pmod{p_{i}^{\alpha_{i}}}$ and $b \equiv b_{i} \pmod{p_{i}^{\alpha_{i}}}$, for $i = 1, 2, \ldots, l$. Therefore,
$$a^{2} - b^{2} + k \equiv a_{i}^{2} - b_{i}^{2} + k \equiv 0 \quad \pmod{p_{i}^{\alpha_{i}}}$$
for all $i = 1, 2, \ldots, l$, and hence
$$a^{2} - b^{2} + k \equiv 0 \quad (\bmod n).$$
On the other hand,
$$\gcd(n, a) = \prod_{i=0}^{l} \gcd(p_{i}^{\alpha_{i}}, a_{i}) = 1 \text{ and } \gcd(n, b) = \prod_{i=0}^{l} \gcd(p_{i}^{\alpha_{i}}, b_{i}) = 1.$$
This completes the proof.