The proof is given here in the answer Proving $(\frac{n}{p})$, a Legendre symbol, is multiplicative

But I do not understand it, Also the definition in the book for Legendre symbol says that if $p|a$ the Legendre symbol $a/p$ is undefined not 0 as in this solution, could anyone give me a more clear proof please?

  • 2
    $\begingroup$ If you mean how to show $(\frac{a}{p})(\frac{b}{p})=(\frac{ab}{p})$ then it follows from that $\Bbb{Z/pZ}^\times$ is cyclic so that $(\frac{a}{p})= a^{(p-1)/2} \bmod p$. The periodicity of $p \mapsto (\frac{q}{p})$ is quadratic reciprocity. $\endgroup$ – reuns Jun 11 at 23:32
  • 4
    $\begingroup$ It's not good enough to say, "I do not understand it", as that gives us no idea what exactly you don't understand, or what help you need. Please edit your question so it's better focussed. $\endgroup$ – Gerry Myerson Jun 11 at 23:37
  • 3
    $\begingroup$ The Legendre symbol is a function of two variables. When we say it's multiplicative, what we really mean is that if we hold the second variable fixed, then it is multiplicative in the first variable. $f(ab,p)=f(a,p)f(b,p)$. $\endgroup$ – Gerry Myerson Jun 11 at 23:48
  • 3
    $\begingroup$ The Legendre symbol is only defined for prime values of the second argument, so it doesn't even make sense to ask for it to be multiplicative in both variables. $f(a,q)$ is only defined as a Legendre symbol if $q$ is a prime. $\endgroup$ – Gerry Myerson Jun 11 at 23:55
  • 1
    $\begingroup$ I have corrected the link @ThomasShelby I am so sorry ..... it is my bad $\endgroup$ – Secretly Jun 15 at 20:25

I am not a number theorist, but it seems that conceptually the best way to see this is group theoretic. In brief, (for $p>2$) the set of squares is a subgroup of the set of non-zero remainders mod p and this subgroup has index 2 . It is therefore normal, and the Legendre symbol is the homomorphism to the corresponding quotient group $\mathbb{Z}/2\mathbb{Z}$. Below I give a proof without group-theoretic language (but, I think, informed by this understanding).

The multiplicativity we are after is

$$(\frac{ab}{p})= (\frac{a}{p}) (\frac{b}{p})=0$$

for all a, b.

First, there are two apporaches to treating the case when at least one of the $a$,$b$ is divisible by $p$. We can exclude them and only prove the above for $a\not\equiv 0 \mod p$, and $b \not\equiv 0 \mod p$.

Alternatively, we can define $(\frac{x}{p})=0$ when $x$ is divisible by $p$. Note that if $a$ is divisible by $p$ then $ab$ is divisible by $p$. Then this means $(\frac{ab}{p})= (\frac{a}{p}) (\frac{b}{p})=0$ for any $b$, and so with this definition we obtain that the multiplicativity property holds as soon one of the entries is divisible by $p$.

Whatever route we choose, it now only remains to prove

$$(\frac{ab}{p})= (\frac{a}{p}) (\frac{b}{p})=0$$

for all $a \not \equiv 0 \mod p$, and $b \not\equiv 0 \mod p$.

The set of non-zero remainders mod $p$ is a of size $p-1$. As a preparation, we establish that there are the same number of (non-zero) squares and non-squares mod p. Indeed, after squaring each reminder $a$ is paired with $-a$ and nothing else since $x^2\equiv d^2$ means $(x-d)(x+d)\equiv 0$ so either $x\equiv d$ of $x\equiv -d$; so the $p-1$ remainders produce $(p-1)/2$ squares.

Now we check multiplicativity. In 3 remaining cases:

1) $a$ and $b$ are both squares mod $p$.

This is an obvious case, since a product of two squares is a square: $$c^2d^2 \equiv (cd)^2 \mod p$$

2) $a$ is a non-square and $b$ is a square.

A product of a square and a non-square is a non-square: if we had $a d^2 \equiv c^2$ then we would have $a\equiv (c d^{-1})^2$.

3) Both $a$ and $b$ are non-squares. We need to show that $ab$ is a square.

Consider the multipication by $a$, acting on the set of reminders mod p. Since it has an inverse (multiplication by $a^{-1}$), it is bijective. As we saw in case 2, multiplication by $a$ takes squares to non-squares. Since the set of squares and non-squares have the same size, this is a bijection from the set of squares to the set of non-squares. This means that it is also a bijection between the complements, i.e. from non-squares to squares. Thus any non-square multiplied by $a$ becomes a square, and we are done.

Remark: Considering multiplication by $a$ is how one can prove existence of $a^{-1}$ in the first place -- the multiplication is injective since $ax\equiv ay$ means $a(x-y)\equiv 0$ means $x\equiv y$; since domain and target coincide, they have the same size, hence the map is bijective and hence it hits 1, so there exists $x$ with $ax=1$; that's the $x=a^{-1}$.


If $p|n$ or $p|m$ then $p|nm$ so $\displaystyle \left( \frac{nm}{p} \right) = 0$ and $\displaystyle \left( \frac{n}{p}\right) = 0$ or $\displaystyle \left( \frac{m}{p}\right) = 0$. So $\displaystyle \left( \frac{nm}{p}\right) = \left( \frac{m}{p}\right)\left( \frac{n}{p}\right) $ if $p|m$ or $p|n$.

If $p \not\mid n$ and $p \not\mid m$ then $p \not\mid nm$ so

$\displaystyle \left( \frac{nm}{p}\right) \equiv (nm)^{p-1/2} \equiv \left( \frac{n}{p}\right)\left(\frac{m}{p} \right)(mod p)$ . But each $\displaystyle \left( \frac{nm}{p}\right)$, $\displaystyle \left( \frac{n}{p}\right)$ and $\displaystyle \left( \frac{m}{p}\right)$ is $-1$ or $1$. so the difference is $0$,$-2$ or $2$.

See also

Apostol, Introduction to analytic number theory.


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.