Math100 said:
Let ## a ## be a primitive root of ## p ##.
Then the integers ## a^{1}, a^{2}, ..., a^{p-1} ## form a reduced residue system modulo ## p ##
such that ## \varphi(p)=p-1 ##, where ## r\in\left \{ 1, 2, ..., p-1 \right \} ##.
This implies ## r\equiv a^{k}\pmod {p} ## for ## 1\leq k\leq p-1 ##.
By Euler's Criterion, we have that
## (\frac{r}{p})=(\frac{a^{k}}{p})\equiv (a^{k})^{\frac{p-1}{2}}\equiv (a^{\frac{p-1}{2}})^{k}\equiv (-1)^{k}\pmod {p} ##.
Since ## gcd(a, p)=1 ##, it follows that ## a^{\frac{p-1}{2}}\equiv -1\pmod {p} ##.
Note that both ## (\frac{r}{p}) ## and ## (-1)^{k} ## are equal to either ## 1 ## or ## -1 ##.
Thus ## \sum_{r=1}^{p-1}\frac{r}{p}=\sum_{k=1}^{p-1}(-1)^{k}=0 ##.
Sorry, but this sounds rather confusing. E.g. you end a sentence with a specification of ##r## that was never mentioned before. Let me explain the ideas behind the statement.
We are looking for remainders modulo a prime ##p##. These form the additive group ##\mathbb{Z}_p=\{0,1,2,\ldots,p-1\}.## If ##a,b\in \mathbb{Z}_p## then ##a+b \pmod{p} ## is again in ##\mathbb{Z}_p##. We have a zero, addition in associative and we have inverse elements: ##a+(p-a) \equiv 0 \pmod{p}.## It is even a commutative group since ##a+b\equiv b+a\pmod{p}.## These conditions altogether make ##\mathbb{Z}_p## and abelian, additive group.
We have even a field ##\mathbb{Z}_p## because we can distributively muliply in ##\mathbb{Z}_p## and all elements
$$
G:=\mathbb{Z}_p^* = \{a\in \mathbb{Z}_p\,|\,\exists \,b\in \mathbb{Z}_p\, : \,a\cdot b=1\}=\{a\in \mathbb{Z}_p\,|\,\operatorname{gcd}(a,p)=1\}=\{1,2,\ldots,p-1\}=\mathbb{Z}_p -\{0\}
$$
except for the zero form a multiplicative group with ##\varphi (p)=p-1## elements. Since all elements in ##\mathbb{Z}_p## are of order ##p## and all elements of ##\mathbb{Z}_p^*## are coprime to ##p##, they all generate ##G.## This means ##G=\{a^k\,|\,0< k< p\}## for every ##a\in G.##
A character from ##G## is a group homomorphism ##\alpha \, : \,G\longrightarrow \mathbb{C}-\{0\}## such that ##\alpha (a)\cdot\alpha (b)=\alpha (a\cdot b)## where ##a,b\in G## and multiplication in ##G## is modulo ##p.## The characters of ##G## form again a multiplicative group by setting ##(\alpha \cdot \beta )(a):=\alpha (a)\cdot \beta (a).## Say this group of characters is ##M.## Let us fix an (primitive) element ##a\in G.## Then every character is defined by its value on ##a.## Say ##\alpha(a)=z.## Then ##\alpha (a^k)=\alpha(a)^k=z^k## and all elements of ##G## are of the form ##a^k.## The neutral element is the principal (trivial) character ##\chi_0## which maps all elements on ##1##. Then ##\alpha^{-1}(a^k):=z^{-1}## defines the inverse character: ##(\alpha \cdot \alpha^{-1})(a)=\alpha (a^k)\cdot \alpha^{-1}(a^k)=z^k\cdot (z^{-1})^k=1^k=1=\chi_0(a^k).## Furthermore, ##\alpha^{p-1}(a)=\alpha(a^{p-1})=\alpha(1)=1=\chi_0(a),## so every character is of finite order and ##z## has to be a ##p-1##-th root of unity. This means we can identify the group of characters of ##G## with ##G=\{1,2,\ldots,p-1\}## itself
The Legendre symbol for ##p\equiv 1\pmod{4}## is quadratic since ##\left(\dfrac{a}{p}\right)\cdot\left(\dfrac{a}{p}\right)=\left(\dfrac{a^2}{p}\right)=1.## We define the subgroup ##G^2=\{a^2\,|\,a\in G\}< G## of all squares modulo ##p## in ##G.##
Let ##a\in G## be a primitive element again. Then ##a## is of even order ##p-1## and ##2n\not\equiv 1\pmod{p-1}.## (Proof: If ##2n\equiv 1\pmod{p-1}## then ##2\,|\,(p-1)\,|\,(2n-1)## which is impossible.) Thus ##(a^n)^2=a^{2n}\neq a## for all ##n\in \mathbb{N}.## This means that ##a## is no square and ##aG^2\neq G^2.## But ##aG^2## is of order ##2## in ##G/G^2=\{G^2,aG^2\}.## It exists therefore exactly one non-trivial homomorphism ##G/G^2\longrightarrow \mathbb{C}-\{0\}## given by ##G^2\longmapsto \chi_0## and ##aG^2\longmapsto \left(\dfrac{\cdot}{p}\right)## the Legendre symbol. Since ##G^2## and ##aG^2## and ##G=G^2\cup aG^2,## we have equally many elements in ##G^2## and ##aG^2##, i.e. we have equally many squares in ##G## as non-squares. Finally,
$$
\sum_{k=1}^{p-1}\left(\dfrac{k}{p}\right)=\sum_{k\in aG^2}\left(\dfrac{k}{p}\right)+\sum_{k\in G^2}\left(\dfrac{k}{p}\right)=\left|aG^2\right|\cdot (-1)+\left|G^2\right|\cdot (+1)=\left|G^2\right|\cdot (-1+1)=0
$$
and
Math100 said:
\begin{align*}
&\sum_{k=1}^{p-1}k(k|p)=\sum_{k=1}^{p-1}(p-k)(p-k|p)\\
&=\sum_{k=1}^{p-1}(p-k)(k|p)\\
&=p\sum_{k=1}^{p-1}(k|p)-\sum_{k=1}^{p-1}k(k|p)\\
&=-\sum_{k=1}^{p-1}k(k|p).\\
\end{align*}
Thus ## \sum_{k=1}^{p-1}k(k|p)=0 ##.
