1
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ Looks good to me. In a sense this is also a proof there are infinitely many primes :) $\endgroup$
    – Sil
    Commented Nov 9, 2022 at 18:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sil
    Commented Nov 9, 2022 at 18:43
  • $\begingroup$ @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! $\endgroup$
    – FlipTack
    Commented Nov 9, 2022 at 18:47
  • 1
    $\begingroup$ Then it should be fine (though I would probably clarify this part in the proof to avoid confusion) $\endgroup$
    – Sil
    Commented Nov 9, 2022 at 18:48
  • 1
    $\begingroup$ Also note this is essentially the same proof as given in Theorem 3 in A Classical Introduction to Modern Number Theory. $\endgroup$
    – Sil
    Commented Nov 9, 2022 at 19:10

1 Answer 1

1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I'm using the Jacobi symbol, a generalisation of Legendre symbols when the integers are not prime. The first identity is true by definition of the Jacobi symbol, in fact (-1/21) = 1. And quadratic reciprocity applies to the Jacobi symbols as long as the top and bottom are both odd. $\endgroup$
    – FlipTack
    Commented Nov 9, 2022 at 18:29
  • 1
    $\begingroup$ Oh sorry about that, I didn't know about Jacobi symbol. I can't find any problems in that case. Btw which number squares to -1 mod 21. $\endgroup$
    – Bahoz M
    Commented Nov 9, 2022 at 18:43
  • 1
    $\begingroup$ nvm I just realised it doesn't necessarly have to be a quadratic residue if the jacobi is 1 $\endgroup$
    – Bahoz M
    Commented Nov 9, 2022 at 18:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .