# Choosing $n$ such that $(n/p) = -1$ for all $p$

Fix a prime $p$. I was wondering if it was possible to choose $n$ such that $(n/p) = -1$ for all $p$?

For example, suppose $p \equiv 3, 5 \pmod{8}$. Then choose $n \equiv 2 \pmod{p}$ would give that $(n/p) = (2/p) = -1$. If $p \equiv 7 \pmod{8}$, then choose $n \equiv -1 \pmod{p}$ would give that $(n/p) = (-1/p) = -1$. However, how does one deal with the $p \equiv 1 \pmod{8}$ case?

-
I guess you meant "fix n", @user61784 ? – DonAntonio Feb 11 '13 at 4:40
I am confused by which of $n$ and $p$ you are fixing and which you are allowing to vary. Could you please clarify this? – Pete L. Clark Feb 11 '13 at 4:40
I think one can make a sensible question out of this by asking whether, for every arithmetic progression containing and missing infinitely many primes, there is an integer $n$ that is a quadratic nonresidue modulo every one of those primes in that progression. – Gerry Myerson Feb 11 '13 at 4:48
@Gerry, I followed my own procedure of making up the question I wished to answer. – Will Jagy Feb 11 '13 at 4:50
@Will, yes, but I think you did manage to answer the $p\equiv1\pmod8$ question. – Gerry Myerson Feb 11 '13 at 4:51

Well, no. For one thing, $n$ has prime factors, at least one, so that Legendre symbol is 0. Other than that, divide out the largest square, so $n = k^2 n_0$ with $n_0$ squarefree, or $$n_0 = p_1 p_2 \cdots p_r.$$

First, for odd $n_0:$ By the Chinese Remainder Theorem, we can find a new prime $q$ such that: $$q \equiv 1 \pmod 4,$$ and each $$q \equiv 1 \pmod {p_j}.$$ By quadratic reciprocity, each $(p_j | q)=1$ and $(n_0 | q) = 1.$

If we now consider $2 n_0,$ all we need to add in is $q \equiv 1 \pmod 8,$ so that 2 is also a residue. This also takes care of a possible factor of $-1.$

-

Let $n$ be an integer.

Theorem: $n$ is a square modulo some prime.

Proof: Consider the polynomial $f(x) = x^2 - n$. Choose any $a$ such that $f(a) \notin \{ -1, 0, 1 \}$. Then there is a prime $p$ such that $p | f(a)$. Thus, we have

$$a^2 \equiv n \pmod p$$

$\square$

-
I'm not sure that's the question OP wants answered. I think OP wants to know whether $n$ is square modulo some prime $p$ with, say, $p\equiv1\pmod8$. But certainly OP could help us out here by clarifying the question. – Gerry Myerson Feb 11 '13 at 6:27
@Gerry: I'm not sure either. – Hurkyl Feb 11 '13 at 6:30