Application of Gauss' lemma

Question

Using Gauss' lemma show when $p$ is an odd prime, one has $$\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}$$

The proof starts with let $a=2$ in gauss' lemma, then one has

$$ a_j = \begin{cases} 2j, & \text{when $1\leq j\leq [p/4]$} \\ 2j-p, & \text{when $[p/4]<j\leq(p-1)/2$} \end{cases} $$

I am not sure where the $[p/4]$ comes from. Can someone break down where the values for $a_j$ come from.

Answer 1

In this lemma $a_j$ gives a specific representant of $2j$ modulo $p$. This is the unique representant between $-\frac{p-1}{2}\leq a_j\leq \frac{p-1}{2}$. Just try for $p=11$ and $p=13$ :

$$p=11 $$

$j=1,...,\frac{p-1}{2}=5$ you get :

$$a_1=2=2\times 1$$

$$a_2=4=2\times 2$$

$$a_3=6=-5=2\times 3-11 $$

$$a_4=8=-3=2\times 4-11 $$

$$a_5=10=-1=2\times 5-11 $$

Hence for $j=1,2$ you have that $2j$ is below $\frac{p-1}{2}$ and for $j=3,4,5$ you have that $2j-p$ is in the good range. Remark that $p/4=2.75$ that is below $2$, $2j$ is okay and above the good representant is $2j-p$.

$$p=13 $$

$j=1,...,\frac{p-1}{2}=6$ you get :

$$a_1=2=2\times 1$$

$$a_2=4=2\times 2$$

$$a_3=6 $$

$$a_4=8=-5=2\times 4-13 $$

$$a_5=10=-3=2\times 5-13 $$

$$a_6=12=-1=2\times 6-13 $$

Answer 2

intuitively, if you take any odd prime, and then get multiple of ${a}$ till ${(\frac{p-1}{2})}$ say, ${\{a,2a,..,a (\frac{p-1}{2})\}}$, you will have some numbers less then ${(\frac{p-1}{2})}$ and some greater than ${(\frac{p-1}{2})}$.

• in p=11 then we've {2,4,6,8,10} but because we're looking for ${(1\le a \le , \frac{p-1}{2})}$, we'll reduce the {6,8,10} to {5-6,5-8,5-10} ={-1,-3,-5}, we can remove the minus sign and replace with ${(-1)^n}$ where n is a count of numbers those are negative. So in our case we've {2,4} are less than ${(\frac{p-1}{2})}$ and {6,8,10} are greater than ${(\frac{p-1}{2})}$.
• Now, in your inequality it states that take numbers of a multiple of 2 till count less than p/4 which is 2 in our case. and for the rest take 2j-p, which is also {6-11,8-11,10-11}={-5,-3,-1}, here ${n=3}$ ,
• ${(\frac{2}{11})=(-1)^3}$ and it is QNR.
• This is how it is derived... all above numbers are now in form of ${((a,2a,...,a(\frac{p-1}{2}))\cdot (-1)^n)}$ i.e., $${a^{\frac{p-1}{2}} \cdot (-1)^n \cdot (\frac {p-1}{2})! \equiv (\frac {p-1}{2})! (mod p)}$$
• cancel factorial and multiply both sides by ${(-1)^n}$ , yields,
• $${a^ \frac{p-1}{2} \equiv (-1)^n (mod p)}$$
• we take only ${(\frac{p-1}{2})}$ in count as after this all the numbers start repeating itself.
• Just for your info as ${p\equiv3(mod8)}$ or ${p\equiv5(mod8)}$, ${(\frac{2}{p} )}$ is always QNR. For p=17, ${(\frac{2}{p} )}$ is QR.