# Prove a property of Legendre symbol

In case someone does not know the definition, I first write down the definition.

Def Let $$a$$ be s.t. $$(a,m)=1$$. Then we say $$a$$ is a quadratic residue modulo m if the congruence $$x^2\equiv a$$ (mod $$m$$) has a solution. If it has no solution, then we say $$a$$ is a quadratic nonresidue modulo m.

Def Let $$p$$ be an odd prime. We define the Legendre symbol $$(\frac{a}{p})$$ to be $$1$$ if $$a$$ is a quadratic residue, $$-1$$ if $$a$$ is a quadratic nonresidue modulo $$p$$, and $$0$$ if $$p|a$$.

I have proven that $$(\frac{a}{p})\equiv a^{(p-1)/2}$$ (mod $$p$$). Now I want to show $$(\frac{a}{p})(\frac{b}{p})=(\frac{ab}{p})$$, but I can only show $$(\frac{a}{p})(\frac{b}{p})\equiv(\frac{ab}{p})$$ (mod $$p$$).

My textbook says that $$(\frac{a}{p})(\frac{b}{p})=(\frac{ab}{p})$$ is just a direct consequence of that $$(\frac{a}{p})\equiv a^{(p-1)/2}$$ (mod $$p$$).

But with the proven equality, we only have that, $$(\frac{a}{p})(\frac{b}{p})\equiv a^{(p-1)/2}b^{(p-1)/2}=(ab)^{(p-1)/2}\equiv (\frac{ab}{p})$$ (mod $$p$$), i.e. $$(\frac{a}{p})(\frac{b}{p})\equiv(\frac{ab}{p})$$ (mod $$p$$), rather than $$(\frac{a}{p})(\frac{b}{p})=(\frac{ab}{p})$$.

And I have a further problem.

My textbook says that, the question to determine whether $$x^2\equiv a$$ (mod $$p$$) does or does not have a solution can be narrowed to the case $$x^2\equiv q$$ (mod $$p$$), where $$a$$ is an arbitrary integer and $$q$$ is a prime.

My second problem is that, how to "narrow" the original question to the last one?

I've been thinking of these problems for a half day. Any help will be greatly appreciated. :)

Observe that both $$\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$$ and $$\left(\frac{ab}{p}\right)$$ are equal to $$0,1$$ or $$-1$$. Therefore if they are congruent modulo a prime $$p>2$$, they are necessarily equal.
As for the second question, if $$a$$ is positive you can write it as a product of primes $$a=q_1\dots q_k$$, and using the formula just shown we get $$\left(\frac{a}{p}\right)=\left(\frac{q_1}{p}\right)\dots\left(\frac{q_k}{p}\right).$$ Hence, if we can compute the Legendre symbol with prime at the top, we can compute it for any positive number at the top. To get any $$a$$, we would also like need to know the value of $$\left(\frac{-1}{p}\right)$$.