Using gauss's lemma to find $(\frac{n}{p})$ (Legendre Symbol)

Sorry if this ends up being long.

So basically, i am trying to understand the proofs of Gauss's lemma for things such as $(\frac{2}{p})$ $(\frac{3}{p})$ etc

For $(\frac{2}{p})$ i am given this proof

We know that $(\frac{a}{p}) = (-1)^n$

So finding $n$ is important here obviously.

$n$ is representative of the number of elements in the set $\{{a,2a,3a,...,\frac{(p-1)}{2}}\}$ between $\frac{p}{2}$ and $p$ for $a=2$ this will be $\{2,4,5,...,(p-1)\}$

Approximately half are less than p/2 and the other half lie between p/2 and p, so it is important to precisely find the middle point.

So if $p = 1+4k$ then $2,4,6...,2k < p/2$ and $p/2 < 2k+2, 2k+4,...,4k$
Therefore $n=k=(p-1)/4$
If $p \equiv 1$ mod $8$ then $n = (p-1)/4$ is even
If $p \equiv 5$ mod $8$ then $n = (p-1)/4$ is odd

so $(\frac{2}{p}) = +1$ If $p \equiv 1$ mod $8$
and
so $(\frac{2}{p}) = -1$ If $p \equiv 5$ mod $8$

Then the proof goes on and does the same thing for $p = 3+4k$, which allows you to solve $(2/p)$ for 3 mod 8 and 5 mod 8

I am having trouble understanding this completely. Mostly, i am wondering where the $p = 1+4k$ comes from. I understand that it comes from $p \equiv 1$ mod $4$ But i am confused as to why they chose mod 4. Perhaps my misunderstandings will become more apparent when I try to create this kind of proof for $(\frac{3}{p})$

So to start off, $a = 3$ so i can create the set $\{3,6,9,..,\frac{3(p-1)}{a}\}$

So with the assumption that approximately half will be less than $p/2$ and half will be greater than $p/2$ I will try to find the middle point.

If $p = 1 + 4k$ then (this is where i believe i mess up, perhaps a number other than 4k should be used. Maybe 6k?)

$3,6,9,..,3k<p/2$ and $p/2 < 3k+3,3k+6,...,6k<p$
Therefore, $n = k=(p-1)/6$.
So i guess right here, i need to determine when $(p-1)/6$ is even and when $(p-1)/6$ is odd.

Well, from looking at the equation i can see that $(p-1) \equiv 0$ mod $12$ will give me and even number. Where i got mod 12 by just multiplying 6 by 2. So just use basic arithmetic to get $p \equiv 1$ mod $12$. So extending on that, $p \equiv 7$ mod $12$ will give me an odd number correct?

From this i can conclude that $(3/p) = 1$ when $p\equiv 1$ mod $12$ and $(3/p) = -1$ when $p\equiv 7$ mod $12$.
Then for the other congruences, i can do the same thing except say perhaps let $p = 5+6k$?

I am guessing this can be extended to work for other $(a/p)$ such as $(\frac{5}{p})$ correct?

Solution 1:

Gauss' lemma tells us to look at the number of negative least residues in the list of numbers

a, 2a, 3a, ..., $\frac{p-1}{2}a$

When that number is even, then $(\frac{a}{p})=1$, when odd, then $(\frac{a}{p})=-1$

Let's have a look at the list for a=2. We have the following list of numbers:

$2, 4, ... , p-1$

Start of this list contains values in the interval $(0, \frac{p}{2})$, which equals their (positive) least residue; the remaining values are in the interval $(\frac{p}{2}, p)$. We are only interested in the number of even numbers that are in the latter interval, as these obviously have negative least residues in the interval $(-\frac{p}{2}, 0)$.

The number of even numbers in the interval $(\frac{p}{2}, p)$ clearly equals the number of integers in the interval $(\frac{p}{4}, \frac{p}{2})$.

This is where mod $8$ comes in: determining whether that number of integers in the interval mentioned is odd or even is most easily done if we know the start integer (first one larger than $\frac{p}{4}$) and the end integer (last one smaller than $\frac{p}{2}$) in the list: for example, when the list starts with an even number and ends with an even number, we know the total number in the list is odd.

So we distinguish 4 cases: $p \equiv 1, 3, -3, -1$ mod 8.

$p \equiv 1$ mod8: $p=1+8k$; start integer is the minimum one larger than $2k+\frac{1}{4}$, thus 2k+1; final integer is the maximum one smaller than $4k+\frac{1}{2}$, thus 4k; the number of integers in [2k+1, 4k] is even, thus $(\frac{2}{p})=1$

$p \equiv -1$ mod8: $p=-1+8k$; the interval now becomes $[2k, 4k-1]$, containing an even number of integers, thus $(\frac{2}{p})=1$

$p \equiv 3$ mod8: $p=3+8k$; the interval becomes $[2k+1, 4k+1]$, containing an odd number of integers, thus $(\frac{2}{p})=-1$

$p \equiv -3$ mod8: $p=-3+8k$; the interval becomes $[2k, 4k-2]$, thus $(\frac{2}{p})=-1$

The same can be done for $a=3$ but now we have to consider the least residues of the following list of numbers:

3, 6, ..., $\frac{p-1}{2}3$

which divides into three subsets of multiples of 3:

if $0<3x<\frac{p}{2}$ then the least residue is positive

if $\frac{p}{2}<3x<p$ then the least residue is negative

if $p<3x<3\frac{p}{2}$ then the least residue is positive again

So we wish to know whether the number of multiples of 3 in the interval $(\frac{p}{2},p)$ is odd or even. Similarly as above for $a=2$, this amounts to looking at the number of integers in the interval $(\frac{p}{6},\frac{p}{3})$. So here's where mod 12 comes in. We look at $p \equiv 1, 5, -5, -1$ mod12 (note that 3 and -3 mod 12 are not primes).

$$ \begin{array}{r|r|l|l|c|c} \text{p mod12} & \text{p} & \text{lower} & \text{upper} & \text{count} & (\frac{3}{p}) \\ \hline 1 & 1+12k & 2k+1 & 4k & even & 1 \\ -1 & -1+12k & 2k & 4k-1 & even & 1\\ 5 & 5+12k & 2k+1 & 4k+1 & odd & -1 \\ -5 & -5+12k & 2k & 4k-2 & odd & -1 \end{array} $$

For $a=5$ we land up in a slightly different situation, as the set of multiples of 5 is split up in 5 parts, two of which are relevant (i.e. they have negative least residues). Summary:

$$ \begin{array}{r|r|l|l|c|l|l|c|c|c} \text{p mod20} & \text{p} & \text{lower > $\frac{p}{10}$} & \text{upper < $\frac{p}{5}$} & \text{count 1} & \text{lower > $3\frac{p}{10}$} & \text{upper < $2\frac{p}{5}$} & \text{count 2} & \text{total} & (\frac{5}{p}) \\ \hline 1 & 1+20k & 2k+1 & 4k & even & 6k+1 & 8k & even & even & 1 \\ 3 & 3+20k & 2k+1 & 4k & even & 6k+1 & 8k+1 & odd & odd & -1 \\ 7 & 7+20k & 2k+1 & 4k+1 & odd & 6k+3 & 8k+2 & even & odd & -1 \\ 9 & 9+20k & 2k+1 & 4k+1 & odd & 6k+3 & 8k+3 & odd & even & 1 \\ -9 & -9+20k & 2k & 4k-2 & odd & 6k-2 & 8k-4 & odd & even & 1 \\ -7 & -7+20k & 2k & 4k-2 & odd & 6k-2 & 8k-3 & even & odd & -1 \\ -3 & -3+20k & 2k & 4k-1 & even & 6k & 8k-2 & odd & odd & -1 \\ -1 & -1+20k & 2k & 4k-1 & even & 6k & 8k-1 & even & even & 1 \end{array} $$

So $(\frac{5}{p}) = 1$ if and only if $p \equiv \pm 1, 9 mod 20$. In this particular case, this can be rephrased to $(\frac{5}{p}) = 1$ if and only if $p \equiv \pm 1 mod 5$.

For $a=7$ there are 7 segments to consider, 3 of which have negative residues: $I_1 = (\frac{p}{14}, \frac{p}{7})$, $I_2 = (3\frac{p}{14}, 2\frac{p}{7})$ and $I_3 = (5\frac{p}{14}, 3\frac{p}{7})$. Summary:

$$ \begin{array}{r|r|l|l|c|l|l|c|l|l|c|c|c} \text{p mod28} & \text{p} & \text{lower $I_1$} & \text{upper $I_1$} & \text{count 1} & \text{lower $I_2$} & \text{upper $I_2$} & \text{count 2} & \text{lower $I_3$} & \text{upper $I_3$} & \text{count 3} & \text{total} & (\frac{7}{p}) \\ \hline 1 & 1+28k & 2k+1 & 4k & even & 6k+1 & 8k & even & 10k+1 & 12k & even & even & 1 \\ 3 & 3+28k & 2k+1 & 4k & even & 6k+1 & 8k & even & 10k+2 & 12k+1 & even & even & 1 \\ 5 & 5+28k & 2k+1 & 4k & even & 6k+2 & 8k+1 & even & 10k+2 & 12k+2 & odd & odd & -1 \\ 9 & 9+28k & 2k+1 & 4k+1 & odd & 6k+2 & 8k+2 & odd & 10k+4 & 12k+3 & even & even & 1 \\ 11 & 11+28k & 2k+1 & 4k+1 & odd & 6k+3 & 8k+3 & odd & 10k+4 & 12k+4 & odd & odd & -1 \\ 13 & 13+28k & 2k+1 & 4k+1 & odd & 6k+3 & 8k+3 & odd & 10k+5 & 12k+5 & odd & odd & -1 \\. -13 & -13+28k & 2k & 4k-2 & odd & 6k-2 & 8k-4 & odd & 10k-4 & 12k-6 & odd & odd & -1 \\ -11 & -11+28k & 2k & 4k-2 & odd & 6k-2 & 8k-4 & odd & 10k-3 & 12k-5 & odd & odd & -1 \\ -9 & -9+28k & 2k & 4k-2 & odd & 6k-1 & 8k-3 & odd & 10k-3 & 12k-4 & even & even & 1 \\ -5 & -5+28k & 2k & 4k-1 & even & 6k-1 & 8k-2 & even & 10k-1 & 12k-3 & odd & odd & -1 \\ -3 & -3+28k & 2k & 4k-1 & even & 6k & 8k-1 & even & 10k-1 & 12k-2 & even & even & 1 \\ -1 & -1+28k & 2k & 4k-1 & even & 6k & 8k-1 & even & 10k & 12k-1 & even & even & 1 \end{array} $$

So $(\frac{7}{p}) = 1$ if and only if $p \equiv \pm 1, 3, 9 mod 28$.