Prepared and presented by rashmi

Content editor nandakumar

Number theory part 08

QUADRATIC CONGRUENCES

Objectives

1.Learns the concept of quadratic congruence

2.Familiarise Legenders sympol

3.Studies the properties of legenders sympols

Introduction

In this unit we discuss in detail quadratic congruence .Euler’s criterion for quadratic residue , Legenders sympols are also going to discuss

Quadratic congruence

We shall now take up in detail the study of solutions of quadratic congruences

....(1)

We know how to solve

.....(2)

Where p is a prime. Note that if p l a, we know (2) is nothing but the linear congruence

. If p = 2 then (2) can be easily solved by considering the parity (i.e. of being even and odd) of a, b and c. Henceforth we assume p2. Thus throughout here p is an odd prime.

We have now the quadratic congruence

Where a, b, c are integers p a prime such that pa andp  2.

Since p a and p is an odd prime

(a, P) = (2, p) = 1

Hence we can rewrite the congruence as

Let .

Hence (2) can be solved if and only if

is solvable for y.

Example 1.Let us solve

... (3)

Since (2, 5) = 1, (3) is equivalent to

The solving (3) reduces to solving

...(4)

But (4) has a unique solution

and y = 2x + 3

is the unique solution of (3).

Thus it suffices to solve the congruence of the form

Euler’s Criterion

Definition.Let p be a prime and a an integer coprimeto p. Then a is called a quadratic residue (mod p) if and only if has a solution. Otherwise a is called quadratic non-residue (mod p).

Note that is solvable for all primes p (in fact for all integers m). Thus 1 is a quadratic residue (mod p) for all primes p.

Also has 2 and 3 as its solutions (mod 5). Hence 4 is a quadratic residue (mod 5).

Theorem 1.(i)If a is a quadratic residue modulo p, then has two solutions.

(ii)If a is a quadratic residue (mod p) then

for some t, 1 t  p-1.

(iii)Any reduced residue system (mode p) consists of quadratic residues that are in the set 12, 22, ... quadratic nonresidues.

Proof: (i)Since a is a quadratic residue (mod p), has a solution say x0

Clearly p-x0 also satisfies the congruence since

Hence x0and p – x0are two solution of .

(ii)If a is a quadratic residue (mod p) and x0 is a solution of the congruence

(x0, p) = 1. But then any integer (mod p) is 0, 1, 2, ... or p -1, for some t, 1 t  p -1.

for some t, 1 t  p -1.

(iii)Since p is an odd prime

are both integers

Also

and so on. Hence any integer a coprimeto p is congruent to one of

Thus, if a is a quadratic residue mod p, then

implying that the possible quadratic residues mod p are amongst .

Let r1, r2, ... rp-1 be any reduced residue system (mod p). If ri is a quadratic residue (mod p), then ri = j2 (mod p) for some j, . Hence exactly can be quadratic residues and remaining must be quadratic non-residues.

Theorem 2 (Euler’s Criterion). An integer a is a quadratic residue (mod p) if and only if .

Proof.Suppose that a is a quadratic (mod p). Then

.

 ...(5)

Therefore, by Fermat’s little theorem,

...(6)

Hence

....(by (5) and (6)).

Conversely, let .

If r is a primitive root (mod p), then 1, r, r2, ... rp-2 form a reduced residuce system (mod p); and for some integer k, 1  k  p -2.

Now,

k must an even integer, say k = 2t

rtis a solution of

Corollary 1.Let r be a primitive root (mod p) then rk is a quadratic residue mod p  k is even.

Corollary 2.An integer a coprimeto p is a quadratic residue or a quadratic non-residue (mod p) according as

Proof.By Fermat’s little theorem

If a is a quadratic residue (mod p), then by theorem 2 (mod p) and is a quadratic non-residue if (mod p).

to find quadratic residues (mod p), we should find the integers

(modp).

Example 2, Let us find quadratic residues (mod 17). By theorem 1 all quadratic residues (mod p) are integers 12, 22, 32, 42, 52, 62, 72, 82 (mod 17).

i.e.1, 4, 9, 7, 8, 2, 15, 13 (mod 17)

1, 2, 4, 7, 8, 9, 13, 15 (mod 17).

Euler’s criterion helps us determine which quadratic congruences have a solution. but, is not practical when p is large due to heavy calculations since we need to compute (mod p).

Legendre Symbols and its Properties

Definition.Let p be an odd prime and a any integer. The legender symbol as defined as

The Legendre symbol in fact is a notation of convenience, introduced by a French mathematician Legendre to facilitate computations with quadratic residues.

Example 3.Since has a solution. So 2 is a quadratic residue (mod 17). Hence = 1.

Example 4.Also, 3 is a quadratic residue (mod 13).

Since has a solution

Example 5.But has no solution: so that 2 is not a quadratic residue (mod 13) .

Remark is not a fraction within paranthesis. It says number of solution ofis .

(2)Euler’s Criterion can be stated as:

If p is an odd prime and a an integer coprimeto p then

.

Properties of Legendre Symbol

Theorem 3.Let p be an odd prime and a, b any integers coprimeto p. Then the following hold:

(i)If , then

(ii)

(iii)

Proof.(i) , then, and .simultaneously have solutions or no solutions i. e. if one of or admits a solution, the other will too. Thus if a (or b) is a quadratic residue (mod p) or a quadratic non-residue (mod p) so will b (or a) be. In other words

(ii)By Euler’s Criterion

Since Legendre symbol takes values -1, 0, or 1 only, we have

(iii)... (by (ii))

Corollary 3(First Supplement to quadratic reciprocity law): If p is an odd prime, then

Proof. Take a = -1 in Remark (2) after definition.

The above corollary enables us prove the infinititude of primes of the form 4k + 1.

Theorem 4.There are infinitely many primes of the form 4k + 1, k an integer.

Proof.Let us suppose that there are only a finite number of primes of the form 4k + 1, say p1, p2, ....p1.

Define

N = (2p1, p2... p1)2 +1

Clearly N is an integer of the form 4k + 1 and is coprime to each of p1, p2... pt. By Fundamental theorem of arithmetic N has a prime factor p. Since p cannot be one of p1, p2, ....ptit must be a prime of the form 4m+3 as all odd primes are either of the form 4k + 1 or 4k +3

(2p1, p2... pt)2-1(mod p)

2p1, p2... ptis a solution of x2 -1 (mod p)

-1 is a quadratic residue (mod p).

But then it contradicts corollary 6 since p is of the form 4m +3. Hence there must be infinitely many primes of the form 4k + 1.

Example 6.has a solution if and only if

For

...(Theorem 3)

....(Euler’s criterion)

Now result follows by Euler’s Criterion.

Example 7.Evaluate

Since 168 = 23, 3, 7

= -1, (-1)3 (1) (-1) = -1.

Summary

In this session we have discussed Eular’s criterion for quadratic congruence ie an integer a is a quadratic residue (mod p) if ana only if

We have also discussed the Legender’s sympols and its properties

Glossary

Quadratic residue: let p be a prime and a an integer coprimeto p. Then a is called a quadratic residue (mod p) if and only if has a solution. Otherwise a is called quadratic non-residue (mod p).

Legender sympol:.Let p be an odd prime and a any integer. The legender symbol as defined as

Quiz

1.There areinfinitely many primes of the form

(a)4k+1(b)8k-1(c)6k+5(d)all the above

2.product of a quadratic residue and a quadratic non residue is

(a)quadratic residue(b)quadratic non residue(c)can’t predict(d)none of these

Answers

  1. (d) all the above
  2. (b) quadratic non residue

FAQ

  1. Explain Fermats theorem?

Answer;if p is a prime and pa then

2.is that eulers criterion practically useful

Answer: Eulers criterion is not offered as a practical test for determining whether a given integer is or is not a quadratic residue the calculation involved are too much cumbersome unless the modulus is small a more effective method of computation is embodied in the quadratic reciprocity law which we will discuss later

assignments

1.solve the following congruence

2.Determine which of the following are solvable

  1. Prove that the Diophantine equation x2=3y2-1 has no integral solution .thus

3y2-1 can never be a perfect square for any integer y