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

up vote 8 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 http://qchu.wordpress.com/2009/09/02/some-remarks-on-the-infinitude-of-primes/.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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