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

Let $a \in \mathbb{N}.$ Prove there are infinitely many primes $p$ satisfying $$\left(\frac{a}{p}\right) =1.$$

Remark: One may need to use the Dirichlet theorem, which states that if $a,m$ are coprime then there exists infinitely many primes $p$ such that $p \equiv a \pmod{m}.$

share|cite|improve this question
up vote 3 down vote accepted

You don't need Dirichlet's theorem. The following more general result is true.

Proposition: Let $f(x) \in \mathbb{Z}[x]$ be a nonconstant polynomial with nonzero constant term. Then there exist infinitely many primes $p$ such that $p | f(n)$ for some $n \in \mathbb{Z}$.

To get the desired result take $f(x) = x^2 - a$.

Proof 1. Euler's proof of the infinitude of the primes carries over to this result. Certainly there exists at least one such prime. If $p_1, ... p_n$ are a finite collection of such primes, then $\frac{f(k f(0) p_1 ... p_n))}{f(0)}$ is relatively prime to each $p_i$ for any $k$, so for sufficiently large $k$ it has a prime divisor not among the $p_i$.

Proof 2. More generally we can replace $f(n)$ by a sequence which grows at most polynomially. See

share|cite|improve this answer

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.