Homework Statement:: Without evaluating the Legendre symbols, prove that ## 1(1|73)+2(2|73)+3(3|73)+\dotsb +72(72|73)=0 ##. (Hint: As ## r ## runs through the numbers ## 1, 2, ..., 72 ##, so does ## 73-r ##.)
If this is really true, then there is nothing to show. ##p=73## is odd and ##73\equiv 1\pmod{4}## so the formula applies to ##73.##Relevant Equations:: Let ## p ## be an odd prime. Then ## \sum_{r=1}^{p-1}r(r|p)=0 ## if ## p\equiv 1\pmod {4} ##.
It is already proven in case the formula is true. Maybe you should prove the formula:Since ## p=73 ## in this problem, how should I prove that ## \sum_{r=1}^{73-1}r(r|73)=0 ##? Given that ## 73=1\pmod {4} ##.
Maybe by substituting ## (r|p)=(-1)^{(p-1)/2}(p-r|p) ## into ## \sum_{r=1}^{p-1}r(r|p)=0 ##? But then we have ## \sum_{r=1}^{p-1}r(r|p)=\sum_{r=1}^{p-1}r(-1)^{(p-1)/2}(p-r|p) ##. How should I proceed from here and simplify to ## \sum_{r=1}^{p-1}r(r|p)=0 ##?Are you sure? We know that ##\displaystyle{\sum_{k=1}^{p-1}\left(\dfrac{k}{p}\right)=0}## for any prime. That would be ## (1|73)+(2|73)+(3|73)+\dotsb +(72|73)=0 ## in your notation.
If this is really true, then there is nothing to show. ##p=73## is odd and ##73\equiv 1\pmod{4}## so the formula applies to ##73.##
It is already proven in case the formula is true. Maybe you should prove the formula:
$$
p\equiv 1\pmod{4} \Longrightarrow \sum_{k=1}^{p-1}\left(\dfrac{k}{p}\right)=0
$$
In that case, you should tell us what you already know and what we could use to prove it, e.g. the quadratic residue theorem.
So ## \sum_{k=1}^{p-1}k\cdot (\frac{k}{p})=[1+72\cdot (\frac{72}{73})]+[2+71\cdot (\frac{71}{73})]+\dotsb +[36\cdot (\frac{36}{73})+37\cdot (\frac{37}{73})]=73+73+\dotsb +73 ##?Smallest test:
\begin{align*}
\left(\dfrac{1}{5}\right)+2\left(\dfrac{2}{5}\right)+3\left(\dfrac{3}{5}\right)+4\left(\dfrac{4}{5}\right)&=
1+2\cdot (-1)+3\cdot (-1)+4\cdot 1=0
\end{align*}
Ok, no counterexample. Let's see what the hint says:
\begin{align*}
\sum_{k=1}^{p-1}k\cdot \left(\dfrac{k}{p}\right)&=\left[1\cdot\left(\dfrac{1}{p}\right)+(p-1)\cdot\left(\dfrac{p-1}{p}\right)\right]+\left[2\cdot\left(\dfrac{2}{p}\right)+(p-2)\cdot\left(\dfrac{p-2}{p}\right)\right]\\
+&\ldots +\left[((p-1)/2)\cdot\left(\dfrac{((p-1)/2)}{p}\right)+((p+1)/2)\cdot\left(\dfrac{((p+1)/2)}{p}\right)\right]
\end{align*}
Can you simplify these terms?
Hint: ##\left(\dfrac{k}{p}\right)=\left(\dfrac{p-k}{p}\right)## if ##p\equiv 1\pmod{4}.## Is the number of brackets ##[\cdot]## even or odd?
No.So ## \sum_{k=1}^{p-1}k\cdot (\frac{k}{p})=[1+72\cdot (\frac{72}{73})]+[2+71\cdot (\frac{71}{73})]+\dotsb +[36\cdot (\frac{36}{73})+37\cdot (\frac{37}{73})]=73+73+\dotsb +73 ##?
That seems to be right. Because ## 73 ## has 36 quadratic residues and 36 non-quadratic residues. So they should cancel each other out leaving the answer to ## 0 ##. Also, earlier you mentioned that there's another theorem which claims ## \sum_{r=1}^{p-1}(r|p)=0 ## for any prime, where both the number of quadratic residue and non residue modulo ## p ## are exactly ## \frac{p-1}{2} ##. And if ## (\frac{k}{p})=(\frac{p-k}{p}) ## for ## p\equiv 1\pmod {4} ##, thenNo.
We get from ##\left(\dfrac{k}{p}\right)=\left(\dfrac{p-k}{p}\right)## for ##p\equiv 1\pmod{4}## that
\begin{align*}
\sum_{k=1}^{p-1}k\cdot \left(\dfrac{k}{p}\right)&=\sum_{k=1}^{(p-1)/2}\left[k\cdot\left(\dfrac{k}{p}\right)+(p-k)\cdot\left(\dfrac{p-k}{p}\right)\right]\\
&=\sum_{k=1}^{(p-1)/2}\left[(k+p-k)\cdot \left(\dfrac{k}{p}\right)\right]=p\cdot\sum_{k=1}^{(p-1)/2}\left(\dfrac{k}{p}\right)
\end{align*}
We get from ##p\equiv 1\pmod{4}## that there are an even number of summands, namely ##\dfrac{p-1}{2} ## many. This means we have to show that there are equally many Legendre symbols with ##+1## as there are with ##-1.##
I assume from the example with ##p=5## that ##\left(\dfrac{k}{p}\right)=-\left(\dfrac{k+1}{p}\right)## if ##k< \dfrac{p-1}{2}.## That would be the easiest way to sort all ##\dfrac{p-1}{2}## summands by pairs of ##+1## and ##-1.## Can you prove this? Or find an argument for why it is true? Or is there another grouping such that
$$
\sum_{k=1}^{(p-1)/2}\left(\dfrac{k}{p}\right)=0\quad ?
$$
Why is this the case?That seems to be right. Because ## 73 ## has 36 quadratic residues and 36 non-quadratic residues.
Very nice!So they should cancel each other out leaving the answer to ## 0 ##. Also, earlier you mentioned that there's another theorem which claims ## \sum_{r=1}^{p-1}(r|p)=0 ## for any prime, where both the number of quadratic residue and non residue modulo ## p ## are exactly ## \frac{p-1}{2} ##. And if ## (\frac{k}{p})=(\frac{p-k}{p}) ## for ## p\equiv 1\pmod {4} ##, then
\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 ##.
From ## \frac{p-1}{2} ##, to find the number of quadratic residues and non-quadratic residues.Why is this the case?
Very nice!
Yes, but we need equally many among the first half, from ##1## to ##\dfrac{p-1}{2}.## That would be ##18## quadratic residues and ##18## quadratic non-residues amongFrom ## \frac{p-1}{2} ##, to find the number of quadratic residues and non-quadratic residues.
I was thoughtless.Yes, but we need equally many among the first half, from ##1## to ##\dfrac{p-1}{2}.## That would be ##18## quadratic residues and ##18## quadratic non-residues among
$$
\left\{\left(\dfrac{1}{73}\right),\left(\dfrac{2}{73}\right),\ldots,\left(\dfrac{36}{73}\right)\right\}
$$
Let ## a ## be a primitive root of ## p ##.Your conclusion in post #7 is fine! (My previous post #10 is only valid if we want to show it directly. So maybe it was me who was thoughtless, not you. I blame it on the time gap.)
Your argument eliminates the coefficients (factors) in front of the Legendre symbols. Unfortunately, the consecutive Legendre symbols ##\left(\dfrac{a}{p}\right),\left(\dfrac{a+1}{p}\right)## do not alternate in general. The case ##p=5## was too small to recognize that. This table shows the distribution: https://en.wikipedia.org/wiki/Legendre_symbol#Table_of_values
So we are left to show that
$$
\sum_{k=1}^{p-1}\left(\dfrac{k}{p}\right)=0.
$$
This is equivalent to what you said: there are equally many quadratic residues as quadratic non-residues among ##\{1,2,\ldots,p-1\}.## Now, why is this the case?
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.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 ##.
\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 ##.
What a long proof. But what does ## aG^{2} \mapsto ({\frac{\cdot }{p}}) ## mean/indicate? I've never seen this before.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