# Is $u$ a quadratic residue mod $t + nu$?

Suppose $u$ and $t$ are positive integers with $\gcd(u,t) = 1$. Is $u$ a quadratic residue mod $t + nu$ for some $n \in \mathbb{Z}$?

The answer is yes in every example that I tried. I was hoping this would follow from quadratic reciprocity, but I don't see how (even assuming $u$ and $t$ are prime). One difficulty I anticipate is that in some cases the numbers $t+nu$ that work can't be primes. For example, if $u = 5$ and $t = 13$, then $t+nu \equiv 3 \mod 5$, but $5$ is not a quadratic residue modulo primes of this form. However, $5$ is a quadratic residue modulo $38 = 13 + 5*5$.

This question arose while trying to ensure a matrix was symplectic.

I don't have a complete characterization but I found a counterexample. In the following, we let $\genfrac(){}{0}{m}{n}$ denote the Jacobi symbol.

We proof that:
Let $(u,t)=(17,3)$, then $u$ is not a quadratic residue for $t+un$ for all $n\in \mathbb Z$.

Proof
Since $17\equiv 1 \pmod 4$, by quadratic reciprocity we have $$\genfrac(){}{0}{17}{3+(2n)(17)}= 1\cdot \genfrac(){}{0}{3+(2n)(17)}{17}=\genfrac(){}{0}{3}{17}=-1$$ since $3$ is not a quadratic residue of $17$. This shows that $17$ is not a quadratic residue of the odd subset $3+(2n)(17)$.

It remains to check the remaining even subset $3+(2n+1)(17)=2(10+17n)$. Suppose that $17$ is a quadratic residue for some $n$, so that $$a^2 = 17 + k\cdot 2(10+17n)$$ Then for each odd prime $p$ dividing $10+17n$, we have $$a^2 \equiv 17 \pmod p$$ i.e. $17$ is a quadratic residue of $p$. We first get a classification of such $p$. Using quadratic reciprocity: $$\genfrac(){}{0}{p}{17} = 1\cdot \genfrac(){}{0}{17}{p} = 1$$ since $17$ is a quadratic residue of $p$. Hence $p$ is a quadratic residue of $17$. We know that $3$ is a generator of $(\mathbb Z/17\mathbb Z)^\times$, therefore we can write $p$ as $$p \equiv 3^{2e} \pmod{17}$$ for some integer $e$.

Now suppose the prime factorization of $10+17n$ is $$p_1p_2\cdots p_m = 10+17n$$ Using the fact that $3$ is a generator, we express $p_i$ as $$p_i \equiv 3^{e_i} \pmod{17}$$ Then noting that $10\equiv 3^3 \pmod{17}$, we obtain \begin{align*} 3^{e_1}3^{e_2} \cdots 3^{e_m} &\equiv 3^3 \pmod{17}\\ e_1+e_2 + \cdots + e_m &\equiv 3 \pmod{\phi(17)=16} \end{align*} where $\phi$ is the Euler Totient function. From the last equation, we cannot have all $e_i$ even as the sum would have been even. Therefore there is some $e_j$ that is odd, corresponding to prime $p_j$. Moreover, since $2\equiv 3^{14} \pmod{17}$, $p_j$ must also be odd (to use the reciprocity earlier).

We now have $17$ is a quadratic residue mod an odd $p_j$, which has odd exponent $e_j$. However we have shown earlier that all such odd $p$ must have even exponent $e$, giving us a contradiction. $$\tag*{\Box}$$

We can find infinitely many counter examples of this type, but I have not found other types of counter examples. Perhaps it may be possible to solve the rest of the cases?