### Definition.

For and , Then , we define say that is residue of nth-degree modulo m , If there exist integer solutions for –

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

For we call it as quadratic, cubic and bi-quadratic residues respectively.

Theorem :

There are quadratic residues in .

Proof :

Consider , These are all quadratic residues ofcourse .

We can also observe that they are also distinct . Indeed, If , , Then ,

Note that ,

Therefore,

and since both are less than –

Hence Proved.

Note : We consider the residue of squares only till because , for

Hence it is enough to consider till .

Thus , there are quadratic residues in – .

Definition :

Legendre‘s Symbol

Let and prime , The Legendre’s Symbol of with respect to is defined by

– If a is a quadratic residue modulo p

– If p divides a

– If a is a quadratic non-residue mod p

Theorem :

For any odd prime –

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

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

Let be the distinct remainders that are less than and let ,

be the remaining distinct remainders. Then we have the following relation –

Proof :

We have –

Since , we also have that –

We claim that there exist no such that –

Indeed, assume otherwise ,

which is not possible as they are both less than

Hence the claim.

Thus ,

Thus,

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

Hence combining this with our result earlier ,we get –

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

Using this, for proving the theorem, let ,

The number of integers k such that – is

Now, checking when , our theorem is proved.