2
$\begingroup$

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. :)

$\endgroup$
3
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ I'm completely clear now. Thank you so much!! $\endgroup$ – Sam Wong May 12 at 11:45

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.