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. 🙂
Best Answer
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)$.