Let $a$ be a positive integer which is not a square, i.e. $a\neq n^2$ for all $n=1,2,3,\ldots$.

Show that there exists an odd prime $p$ such that $\left(\frac{a}{p}\right)=-1.$

Hint: You may use "Dirichlet's theorem on Primes in Arithmetic Progressions" which says; Let $m,r$ be positive integers such that $(m,r)=1.$ Then there are infinitely many primes among the integers $mk+r$, $k=1,2,3,\ldots$.

What I have done is that suppose that there isn't an odd prime which makes Legendre symbol -1 for given a, When p is much lager than a, it can't be 1... well I don't know how to prove such p is a prime.


If $2$ is the only prime that divide $a$ with an odd multiplicity it is enough to consider a prime $p\equiv \pm 3\pmod{8}$ that does not divide $a$.

Assume that $q_1 < q_2 <\ldots < q_k$ are the primes that divide $a$ with an odd multiplicity.

Let $\eta_k$ be the least non-quadratic residue $\!\!\pmod{q_k}$: prove that $\eta_k$ is a prime.

Now take a prime $p\equiv 1\pmod{8},p\equiv 1\pmod{q_1},p\equiv{1}\pmod{q_2},\ldots ,p\equiv 1\pmod{q_{k-1}}$, $p\equiv\eta_k\pmod{q_k}$. You are allowed to do that since by the Chinese theorem the previous constraints are equivalent to $p\equiv N\pmod{2^m\prod q_i}$ and Dirichlet's theorem applies. Then:

$$\left(\frac{a}{p}\right) = \prod_{j=1}^{k}\left(\frac{q_j}{p}\right) = \prod_{j=1}^{k-1}\left(\frac{p}{q_j}\right)\cdot\left(\frac{\eta_k}{q_k}\right)=\color{red}{-1}$$ by quadratic reciprocity and the multiplicative property of the Legendre symbol.

  • $\begingroup$ For the first case, you can't technically use $p=5$ if $a = 50$. But of course one can switch to another prime that is $\equiv 3,5 \pmod 8$. $\endgroup$ – Erick Wong Jun 3 '16 at 4:17
  • $\begingroup$ By chinese remainder theorem. We can make p which makes legendre symbol -1 as you did but, how can i prove that sucb p is odd prime?? $\endgroup$ – nien Jun 3 '16 at 5:01
  • $\begingroup$ @nien: the constraint $p\equiv 1\pmod{8}$ ensures that. $\endgroup$ – Jack D'Aurizio Jun 3 '16 at 11:50
  • $\begingroup$ well if we look just $p \equiv 1 \pmod8$, we can think that there are many primes such form by dirichlet's theorem because of (1,8)=1 but in this, we don't just look $p \equiv 1 \pmod8$ but we have to also look (p=1 mod8 and p=1 modq1 , p=1 modq2 ... p=1 modq(k-1) and finally p=nk mod qk. we can make p by chinese remainder theorem but if we want to check there is such p (after chiniese remainder theorem), we have to at least check that 8q1q2q3...qk and p is relatively prime. anyway, i need that the number that you made is really prime! by dirichlet's theorem $\endgroup$ – nien Jun 3 '16 at 11:58
  • $\begingroup$ @nien: $q_1,\ldots,q_k$ are distinct primes and $\eta_k< q_k$, hence $N$ is for sure coprime with $\text{lcm}(8,q_1,\ldots,q_k)$ and Dirichlet's theorem applies, as written above. $\endgroup$ – Jack D'Aurizio Jun 3 '16 at 12:00

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.