# Legendre symbol- what is the proof that it is a homomorphism?

I know that one property of the Legendre symbol is that it is a homomorphism. However, I have not been able to find a proof that this is the case. If someone could give me or show me to a thorough proof of this, that would be great.

I am going with the definition:

$\sigma(x) = 1$ when $x=y^2$

$\sigma(x)= -1$ otherwise

where $\sigma$ is a map st $\sigma: {\mathbb{Z}_p}^{\times} \rightarrow (-1,1)$

EDIT: How would we sketch a proof that the symbol is a homomorphism using that

if $(G, *)$ is a finite group and $H\subset G$ is a subgroup, and we have an equivalence relation on $G: x \sim y$ iff $\exists h \in H$ st $y= x*h$, and $P$ is an equivalence relation: then we know $\# P = \# H$ and $\# H$ divides $\# G$.

Basically how would we prove, using this fact, that the set of squares in $\mathbb{Z}_p$ is a subgroup of $\mathbb{Z}_p$?

-
Depends a bit on what definition you start with. –  Gerry Myerson Feb 18 '13 at 1:18

Let $p$ be a fixed odd prime. Then for $a$ and $b$ relatively prime to $p$, we have $(ab/p)=(a/p)(b/p)$ (the product of two residues or non-residues is a residue, the product of a non-residue and a residue is a non-residue). Thus the Legendre symbol induces a homomorphism from the multiplicative subgroup of $\mathbb{Z}_p$ to its multiplicative subgroup $\{1,-1\}$.

Remark: We sketch a proof of the key fact about products of residues and/or non-residues. We will need the fact that there are $(p-1)/2$ residues, and therefore $(p-1)/2$ non-residues.

(a) Let $f(x)$ be the map that takes $x$ to $x^2$. For any $a\in \mathbb{Z}_p$, the equation $f(x)=a$ has two solutions or no solutions. For suppose that $b^2\equiv a \pmod{p}$. Then $(-b)^2\equiv a \pmod{p}$, so there are at least two solutions. But if $c^2-b^2\equiv 0\pmod{p}$, then $(c-b)(c+b)$ is divisible by $p$, and therefore $c\equiv b\pmod{p}$ or $c\equiv -b\pmod{p}$, so there are no more than $2$ solutions.

Since the mapping $f$ is two-to-one, its range has size $(p-1)/2$, so $p$ has $(p-1)/2$ QR.

(b) Let $a$ be a QR and let $b$ be an NR. We show that $ab$ is an NR. Suppose to the contrary that $ab$ is a QR. We have by assumption that $a\equiv c^2\pmod{p}$ for some $c$, and that $ab\equiv d^2\pmod{p}$ for some $d$. Thus $c^2b\equiv d^2\pmod{p}$. Multiply twice by the inverse of $c$ modulo $p$. We get that $b\equiv (c^{-1}d)^2\pmod{p}$, contradicting the fact that $b$ is an NR.

The proof that a product of QR is a QR is even easier.

(c) To show that an NR times an NR is a QR, let $b$ be an NR. Then as $x$ ranges over the multiplicative subgroup of $\mathbb{Z_p}$, so does $bx$. Since $b$ times a QR is an NR, and there are equal numbers of QR and NR, we must have that $bx$ is a QR whenever $x$ is an NR.

-
Ah! Maybe I should clarify. How can we prove $(ab/p)=(a/p)(b/p)$ as well? Additionally I should mention that I just started abstract algebra... I do not see how it is clear that the product of residues is a residue. –  Johann Linus Feb 18 '13 at 1:36
I think you meant to say that a non-residue times a non-residue is a residue, and that a non-residue times a residue is a non-residue, in the last paragraph. It's generally a little sketchy (why are there as many residues as non-residues?), which isn't good, since it's the least obvious part. –  tomasz Feb 18 '13 at 2:15
@JohannLinus: I have added detail, and fixed a couple of bad typos. Did not show QR times QR is QR, since that is the easiest, so I will do it here. Suppose $a$ and $b$ are QR. Then there are $c$ and $d$ such that $a\equiv c^2\pmod{p}$ and $b\equiv d^2\pmod{p}$. But then $ab\equiv (cd)^2\pmod{p}$. –  André Nicolas Feb 18 '13 at 3:36
@tomasz: Thanks for the spotting the unfortunate reversal. I have added a reasonably full sketch of everything, including, at your suggestion, a proof of the fact there are $(p-1)/2$ QR and $(p-1)/2$ NR. –  André Nicolas Feb 18 '13 at 3:39

I am wondering if it is permissible to use the primitive roots modulo a prime $p$.
Suppose so, and then we look at the definition of a Legendre symbol, and then give a proof that it is a homomorphism. So fix a prime $p$ first.
Let $x$ be a number not divisible by $p$. Suppose that we already have at disposal a primitive root modulo $p$, denoted by $g$. Then it is easily seen that $g$ is a non-residue of $p$, and that every integer is congruent to $g^n$ for some $n$. Moreover, $x$ is a residue if and only if $x\equiv g^{2k}$ for some $k$. Then the fact that Legendre symbol is a homomorphism follows from the rules that even+even=even, even+odd=odd, and that odd+odd=even.
Suppose we are not given the existence of a primitive root modulo $p$. Then we use another approach:
Let $p$ be an odd prime. Define a homomorphism from $\mathbb Z_p^*={1, \cdot\cdot\cdot,p-1}$ to itself by squaring: we send $x$ to $x^2$. Its kernel, that is, {$x: x^2\equiv 1\pmod p$}, consists of two numbers: $1$ and $p-1$. Its image is the set of residues modulo $p$, which is also a group $\mathbb S_p$ under multiplication. Since multiplication of integers is abelian, the group $\mathbb S_p$ is a normal subgroup of $\mathbb Z_p^*$. So we can form a quotient $\mathbb Z_p^*/\mathbb S_p$. It is of order $2$, hence isomorphic with the cyclic group of order $2$, {$1,-1$}. And we send $x\in \mathbb Z_p^*$ to its image in $\mathbb Z_p^*/\mathbb S_p$: this is the Legendre symbol. By this definition, it is obvious that Legendre symbol is a homomorphism.
I wonder also if we can talk about the wonderful interpretation due to Zolotarev: it is nothing but the theory of permutations, yet is a magic observation.

-

I feel I should add here a standard result of group theory: a subset of a finite group closed under multiplication is a subgroup. Since $(\Bbb Z_p)^{\times}$ is clearly finite, it suffices to show that a QR times a QR is a QR, and the other cases are unnecessary.

Note that the map $x \to x^2$ is an ONTO multiplicative homomorphism from $(\Bbb Z_p)^{\times}$ to the set of quadratic residues (mod $p$) which has kernel $\{1,p-1\}$. This shows that the index of the subgroup of quadratic residues is $2$, which means there must be $\dfrac{p-1}{2}$ quadratic residues (assuming $p$ is an odd prime, this formula breaks down for $p = 2$).

Since NR is thus the "other coset", the other rules for the products:

NR*NR, NR*QR

follow from the rules of coset multiplication in $(\Bbb Z_p)^{\times}/QR$

-