6
$\begingroup$

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

  • 0
    Related: https://math.stackexchange.com/questions/10195382018-11-23

1 Answers 1

9

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