Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $a \in \mathbb{N}.$ Prove there are infinitely many primes $p$ satisfies $$\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|improve this question

1 Answer 1

up vote 2 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/.

share|improve this answer

Your Answer

 
discard

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.