Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Depends a bit on what definition you start with. –  Gerry Myerson Feb 18 '13 at 1:18
add comment

3 Answers 3

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.

share|improve this answer
    
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
1  
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
1  
@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
add comment

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.

share|improve this answer
    
add comment

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$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.