Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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.$

share|cite|improve this answer

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


share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.