# Existence of prime which makes Legendre symbol -1

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.

• 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$. – Erick Wong Jun 3 '16 at 4:17
• 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?? – nien Jun 3 '16 at 5:01
• @nien: the constraint $p\equiv 1\pmod{8}$ ensures that. – Jack D'Aurizio Jun 3 '16 at 11:50
• 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 – nien Jun 3 '16 at 11:58
• @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. – Jack D'Aurizio Jun 3 '16 at 12:00