# Legendre symbol problem

This is a part of my HW. Let $p$ be an odd prime and $a$ an integer coprime to $p$. I am asked to show that $$(\frac{a}{p})+(\frac{2a}{p})+\cdots+(\frac{(p-1)a}{p} )= 0.$$ I got no idea to solve it . Could someone give me a help ? Thanks in advance.

## 3 Answers

First of all, consider the set of reduced residues $\pmod p,S:\{1,2,\cdots,p-2,p-1\}$.

Now, if $g$ is primitive root of the odd prime $p,$ which has $\phi(p)=p-1$ primitive roots.

So, $ord_pg=\phi(p)=p-1$

If $g^i\equiv g^j\pmod p$ where $i>j$

$g^{i-j}\equiv1\pmod p\iff (p-1)\mid (i-j)$ as $ord_pg=p-1$

So, each distinct power $\in [1,p-1]$ of $g$ is congruent to exactly one element of $S$.

We know the quadratic residues are $g^2,g^4,\cdots g^{p-1}\equiv1$. So, there are $\frac{p-1}2$ quadratic residues and $p-1-\frac{p-1}2=\frac{p-1}2$ number of quadratic non-residues.

Consequently, $\sum_{1\le r\le p-1}\left(\frac r p\right)=0$

• May I request for a review? – lab bhattacharjee Dec 11 '12 at 15:18

We know that $\displaystyle\left(\frac{ar}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{r}{p}\right)$.

So, $\displaystyle\sum_{r=1}^{p-1}\left(\frac{ar}{p}\right)=\left(\frac{a}{p}\right)\sum_{r=1}^{p-1}\left(\frac{r}{p}\right)$.

The number of quardratic residues $\displaystyle\pmod{p}$ in $\displaystyle\mathbb{Z}_p\setminus\{0\}$ is $\displaystyle\frac{p-1}{2}$ as well as the number of non-quadratic residues is $\displaystyle\frac{p-1}{2}$.

Hence $\displaystyle\sum_{r=1}^{p-1}\left(\frac{r}{p}\right)=0$. Thus the result follows.

This is basically the same idea as lab's but from another point of view, using the well known properties of the Legendre's symbol.

Put $\,\Bbb F_p^*:=\left(\Bbb Z/p\Bbb Z\right)^*:=\Bbb F_p\setminus \{0\}\,$ , and define

$$T:\Bbb F_p^*\rightarrow \{-1\,\,,1\}\subset \Bbb C^*\;\;,\;\;T(a):=\left(\frac{a}{p}\right)$$

where $\,\{-1\,,\,1\}\,$ is the multiplicative cyclic group of order two. It follows at once $\,T\,$ is a group epimorphism and its kernel it exactly the set (in fact, subgroup) $\,\left(\Bbb F_p^*\right)^2\,$of all quadratic residues modulo $\,p\,$, so by the first isomorphism theorem we get

$$\left|\Bbb F_p^*/\left(\Bbb F_p^*\right)^2\right|=2$$

from which it follows that the number of quadratic residues mod $\,p\,$ equals the number of non-quadratic residues mod $\,p\,$

• Intuituvely I know that T is a group epimorphism, but how can I prove that in fact this is true?, I mean, I know that $1$ have preimage, but I don't know how to guarantee that $-1$ always have a preimage if p is an odd prime – Elmo goya Nov 12 '12 at 18:57