2
$\begingroup$

Is there a proof that for any number $a$, there must be at least one prime $p$ such that $(a/p)=-1$, where $(a/p)$ is the Legendre symbol?

In other words, for all $a$, is there at least one prime $p$ such that $a$ is a quadratic nonresidue modulo $p$?

EDIT: Due to the comments pointing out that there is no such $p$ for $a=x^2$, my question remains the same, except for only all $a\neq x^2$.

$\endgroup$
  • 5
    $\begingroup$ What about $a=1$? $\endgroup$ – Somos Dec 30 '18 at 0:39
  • 5
    $\begingroup$ Or any other square, for that matter. $\endgroup$ – Robert Israel Dec 30 '18 at 0:42
  • $\begingroup$ See here and its linked questions for related results. $\endgroup$ – Bill Dubuque Dec 30 '18 at 23:00
2
$\begingroup$

Here is an interesting exercise that appears in A Classical Introduction to Modern Number Theory.

Let $a$ be a non square integer. Then there are infinitely many primes $p$ for which $a$ is a quadratic non residue.

As a hint, use the Chinese Remainder Theorem in a clever way.

$\endgroup$
  • $\begingroup$ Thank you for the reference. May you provide a proof of the exercise as the book is behind a pay barrier? $\endgroup$ – Tejas Rao Dec 30 '18 at 2:08
  • $\begingroup$ Try your best and after a few days I can give you another hint if needed. $\endgroup$ – Sandeep Silwal Dec 30 '18 at 2:11
0
$\begingroup$

Here is a solution to the above post.

Set $a=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ be prime decomposition of $a$. Clearly, there is a $j$ such that, $\alpha_j$ is odd. Without loss of generality, assume $j=1$. Also, suppose $p_1\neq 2$, which is a case that can be handled separately.

We will construct a prime $p$, such that $p$ is a quadratic residue modulo $p_i$, for every $i \geq 2$, and is not a quadratic residue in modulo $p_1$. Take $a_1$ to be a quadratic non-residue in modulo $p_1$. Take $q_2,\dots,q_k$ to be quadratic residues in modulo $p_k$. Now, there is a prime $p$ such that $p\equiv a_1\pmod{p_1}$, and $p\equiv q_i\pmod{p_i}$, and $p\equiv 1\pmod{4}$, for $i \geq 2$. Existence of this prime is due to Chinese remainder theorem + Dirichlet's theorem.

Finally, by quadratic reciprocity, it is not hard to check, $p$ is a quadratic residue in mod $p_j$ for $j\geq 2$, and a non-residue in mod $p_1$. Construction is complete.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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