Quadratic Residues – I

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 pi=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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: