### Definition.

For $a,m \in {N}$ and $G.C.D (a,m) =1$ , Then , we define say that $a$ is residue of nth-degree modulo m , If there exist integer solutions for –  ${N}$

$x^n \equiv a (mod n)$

Otherwise, It is non-residue of nth-degree modulo m.

For $n=2,3,4 ..$ we call it as quadratic, cubic and bi-quadratic residues respectively.

Theorem :

There are $\frac{p-1}{2}$ quadratic residues in ${1,2,3,...,p-1}$.

Proof :

Consider $k^2 : k=1,2,3, .. , \frac{p-1}{2}$ , These are all quadratic residues ofcourse .

We can also observe that they are also distinct . Indeed, If , $i^2 \equiv j^2 (mod p)$ , Then ,

$p|i^2-j^2 \implies p|(i-j)(i+j)$

Note that , $i,j \le \frac{p-1}{2} \implies i+j \le p-1 < 1$

Therefore,

$p | i-j$ and since both are less than $p$$i=j$

Hence Proved.

Note : We consider the residue of squares only till $\frac{p-1}{2}$ because , for $k \le p$

$\frac{p+k}{2} \equiv - (\frac{p-k}{2}) (mod p)$

$\implies (\frac{p-1}{2})^2 \equiv (\frac{p+1}{2})^2 (mod p)$

Hence it is enough to consider till $\lfloor\frac{p}{2}\rfloor$.

Thus , there are $\frac{p-1}{2}$ quadratic residues in – ${1,2,...,p-1}$ .

Definition :

Legendre‘s Symbol

Let $a,p \in N$ and $p$ prime , The Legendre’s Symbol of $a$ with respect to $p$ is defined by

$(\frac{a}{p}) = 1$ – If a is a quadratic residue modulo p

$(\frac{a}{p}) = 0$ – If p divides a

$(\frac{a}{p}) = -1$ – If a is a quadratic non-residue mod p

Theorem :

For any odd prime –

$(\frac{2}{p}) = (-1)^{\frac{p^2-1}{8}}$

To Prove this theorem, we shall first have a look at what is called the – Gauss’s Lemma

If $a$ is an integer not divisible by $p$ , then by division lemma we have –

$ka = pq_k + r_k \\ k = 1,2,3,..,\frac{p-1}{2}$

Let $b_1,b_2,b_3,...,b_n$ be the distinct remainders that are less than $\frac{p}{2}$ and let ,

$c_1,c_2,c_3,..,c_n$ be the remaining distinct remainders. Then we have the following relation –

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

Proof  :

We have –

$\prod_{i=1}^m b_i \prod_{j=1}^n c_j = \\ \\ \prod_{k=1}^{\frac{p-1}{2}} r_k = \\ \\ \prod_{k=1}^{\frac{p-1}{2}}(ka-pq_k) \\ \\ \equiv \prod_{k=1}^{\frac{p-1}{2}}ka = \\ \\ a^{\frac{p-1}{2}}(\frac{p-1}{2})! (mod p)$

Since , $\frac{p}{2} \le c_j \le p-1$ we also have that – $1 \le p-c_j \le p-1$

We claim that there exist no $i,j$ such that –

$b_i + c_j = p$

Indeed, assume otherwise ,

$p = xa -pq_x + ya - pq_y \implies p | x+y$ which is not possible as they are both less than $\frac{p-1}{2}$

Hence the claim.

Thus ,

$\{b_i} \cup {c_j} = {1,2,...,\frac{p-1}{2}$

Thus,

$\prod_{i=1}^m b_i \prod_{j=1}^n (p-c_j) \equiv (\frac{p-1}{2})!$

Finally , since there are n terms of $latex (p-c_j)$ , we have –

$(-1)^n \prod_{i=1}^m b_i \prod_{j=1}^n (c_j) \equiv (\frac{p-1}{2})! (mod p)$

Hence combining this with our result earlier ,we get –

$a^{\frac{p-1}{2}} \equiv (-1)^n (mod \ p)$

Now, using Euler’s Criterion, our lemma is proved.

Using this, for proving the theorem, let $a=2$,

The number of integers k such that – $\frac{p}{2} \le 2k \le p$ is $\lfloor \frac{p}{2} \rfloor - \lfloor \frac{p}{4} \rfloor$

Now, checking when $p = 4u+1,4u+3$ , our theorem is proved.