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.


1 Answer 1


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

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?


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .