How to prove that the Legendre symbol is multiplicative?

2.8k Views Asked by At

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

There are 2 best solutions below

0
On BEST ANSWER

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

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

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

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

  1. 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}$.

0
On

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.