# Proving $(a/p) = -1$ for infinitely many $p$, without Dirichlet's Theorem.

I'm trying to find a proof of the following claim, without using Dirichlet's Theorem on the arithmetic progression of primes:

Claim: If $$a$$ is not a square, then there are infinitely many odd primes $$p$$ such that $$\left(\frac ap\right) = -1$$.

Note $$(a/p)$$ represents the Legendre symbol. Here's my current attempt:

Proof: Clearly it suffices the prove the case where $$a$$ is squarefree. To begin with, let us prove the case where $$a$$ is odd.

Suppose we have already found such primes $$p_1, \ldots, p_k$$. Prime-factorise $$a = r_1 \ldots r_s$$ and note that $$\left( \frac a{p_i} \right) = -1 \implies (p_i, r_j) = 1 \ \ \forall i,j$$ Moreover, these are all odd primes, so all coprime to $$8$$. Thus by the Chinese Remainder Theorem, we can find $$N > 1$$ such that: $$\begin{cases}N \equiv 1 \ (\text{mod} \ 8) \\ N \equiv 1 \ (\text{mod} \ p_i) \ \forall i \\ N \equiv 1 \ (\text{mod} \ r_j) \ \forall j < s \\ N \equiv c \ (\text{mod} \ r_s) \end{cases}$$

where $$c$$ is any quadratic non-residue modulo $$r_s$$.

Prime-factorise $$N = q_1 \ldots q_l$$. Then by construction these are all odd primes, and $$q_i \ne p_j \ \forall i,j$$.

Since $$a$$ is odd and $$N \equiv 1 \ (\text{mod} \ 4)$$, quadratic reciprocity gives:

$$\prod_i \left(\frac a{q_i}\right) = \left(\frac{a}{N}\right) = \left(\frac{N}{a}\right) = \prod_{j=1}^{s-1} \left(\frac{N}{r_i}\right) \cdot \left(\frac{N}{r_s}\right) = \prod_{j=1}^{s-1} \left(\frac{1}{r_i}\right) \cdot \left(\frac{c}{r_s}\right) = -1$$

So at least one of the terms in the product is $$\left(\frac{a}{q_i}\right) = -1$$, so $$p_{k+1} = q_i$$ is a new such prime, and the result is proven for $$a$$ odd.

Furthermore, we chose $$N \equiv 1 \ (\text{mod} \ 8)$$, so $$\prod_j \left(\frac{2a}{q_j}\right) = \left(\frac{2}{N}\right)\left(\frac{a}{N}\right) = \left(\frac{a}{N}\right) = -1$$

and so by a similar argument the result follows for $$a' = 2a$$, hence for all even squarefree numbers.

Is this proof valid? If so, can it be condensed or improved in any way?

• Looks good to me. In a sense this is also a proof there are infinitely many primes :)
– Sil
Commented Nov 9, 2022 at 18:36
• I am only a bit suspicious about the CRT, you assume the output to be square free in the following factorization, which is not ensured. About condensation, I have not much ideas but first three congruence for CRT can be combined to one actually, probably won't help much.
– Sil
Commented Nov 9, 2022 at 18:43
• @Sil I didn’t intend the $q_i$ to be necessarily distinct - and I don’t think I implicitly used that anywhere - but I will check again! Commented Nov 9, 2022 at 18:47
• Then it should be fine (though I would probably clarify this part in the proof to avoid confusion)
– Sil
Commented Nov 9, 2022 at 18:48
• Also note this is essentially the same proof as given in Theorem 3 in A Classical Introduction to Modern Number Theory.
– Sil
Commented Nov 9, 2022 at 19:10

A problem with the proof is that the construction of $$N$$ with CRT doesn't necessarily mean that it will also be squarefree (this was required when using quadratic residues in the proof). Also it's not true that $$\left(\frac{a}{p_{1}}\right) \left(\frac{a}{p_{2}}\right) = \left(\frac{a}{p_{1}p_{2}}\right)$$. A counter example being that $$\left(\frac{-1}{3}\right) = -1$$ and $$\left(\frac{-1}{7}\right) = -1$$ which means $$\left(\frac{-1}{3}\right)\left(\frac{-1}{7}\right) = 1$$. But $$\left(\frac{-1}{21}\right) = -1$$. Finally quadratic residue only applies when the top and the bottom of the legendre symbol are prime, so we can't have $$\left(\frac{a}{N}\right) = \left(\frac{N}{a}\right)$$.