Without evaluating the Legendre symbols, prove the following....

In summary, we discussed the problem of proving that the sum of Legendre symbols from 1 to p-1 is equal to 0, given that p is an odd prime and p is congruent to 1 mod 4. We used the fact that there are an equal number of quadratic residues and non-residues modulo p, and that the Legendre symbol of k and p-k are equal for p congruent to 1 mod 4. This led us to the conclusion that the sum of k(k|p) from 1 to p-1 is equal to 0.
  • #1
Math100
783
220
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 ##.)
Relevant Equations
Let ## p ## be an odd prime. Then ## \sum_{r=1}^{p-1}r(r|p)=0 ## if ## p\equiv 1\pmod {4} ##.
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} ##.
 
Physics news on Phys.org
  • #2
Math100 said:
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 ##.)

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.

Math100 said:
Relevant Equations:: Let ## p ## be an odd prime. Then ## \sum_{r=1}^{p-1}r(r|p)=0 ## if ## p\equiv 1\pmod {4} ##.
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.##
Math100 said:
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} ##.
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.
 
  • Like
Likes topsquark
  • #3
fresh_42 said:
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.
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 ##?
 
  • #4
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?
 
Last edited:
  • Like
Likes topsquark
  • #5
fresh_42 said:
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?
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 ##?
 
  • #6
Math100 said:
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 ##?
No.

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 ?
$$
 
  • Like
Likes Math100
  • #7
fresh_42 said:
No.

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 ?
$$
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} ##, 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 ##.
 
  • Like
Likes fresh_42
  • #8
Math100 said:
That seems to be right. Because ## 73 ## has 36 quadratic residues and 36 non-quadratic residues.
Why is this the case?
Math100 said:
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 ##.
Very nice!
 
  • Like
Likes Math100
  • #9
fresh_42 said:
Why is this the case?

Very nice!
From ## \frac{p-1}{2} ##, to find the number of quadratic residues and non-quadratic residues.
 
  • #10
Math100 said:
From ## \frac{p-1}{2} ##, to find the number of quadratic residues and non-quadratic residues.
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\}
$$
 
  • Like
Likes Math100
  • #11
fresh_42 said:
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\}
$$
I was thoughtless.
 
  • #12
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?
 
Last edited:
  • Informative
Likes Math100
  • #13
fresh_42 said:
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?
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 ##.
 
  • #14
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 ##.
 
Last edited:
  • Informative
Likes Math100
  • #15
fresh_42 said:
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
What a long proof. But what does ## aG^{2} \mapsto ({\frac{\cdot }{p}}) ## mean/indicate? I've never seen this before.
 

FAQ: Without evaluating the Legendre symbols, prove the following....

1. What are Legendre symbols?

Legendre symbols are mathematical symbols used to express the quadratic character of a number in relation to a prime number. They are denoted by (a/p), where a is an integer and p is a prime number.

2. Why is it important to not evaluate Legendre symbols?

Evaluating Legendre symbols can be time-consuming and complex, especially for larger numbers. Therefore, it is often more efficient and practical to prove properties or relationships involving Legendre symbols without actually evaluating them.

3. How can you prove a statement about Legendre symbols without evaluating them?

There are various mathematical techniques and properties that can be used to prove statements about Legendre symbols without actually calculating their values. These include properties such as the law of quadratic reciprocity and the properties of quadratic residues and non-residues.

4. Can you provide an example of a proof involving Legendre symbols without evaluation?

Sure, for example, to prove that (3/p) = (p/3) for an odd prime number p, we can use the law of quadratic reciprocity, which states that (p/q)(q/p) = (-1)^((p-1)/2)((q-1)/2). Substituting p = 3 and q = p, we get (3/p)(p/3) = (-1)^((3-1)/2)((p-1)/2) = (-1)^p = -1. Since (3/p) and (p/3) are both either 1 or -1, this means that (3/p) = (p/3).

5. Are there any other applications of Legendre symbols besides number theory?

Yes, Legendre symbols have applications in various fields such as cryptography, coding theory, and statistics. They are also used in algorithms for primality testing and factorization of large numbers.

Back
Top