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.
There are quadratic residues in .
Consider , These are all quadratic residues ofcourse .
We can also observe that they are also distinct . Indeed, If , , Then ,
Note that ,
and since both are less than –
Note : We consider the residue of squares only till because , for
Hence it is enough to consider till .
Thus , there are quadratic residues in – .
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
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 –
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.
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.