# Congruence Solutions

Let т,тг,......m, be pairwise relatively prime positive integers. We want

to find the solution of the following system: x = a modmh x = a1 modm2, ..., x = armodmr One method to find the solution of such equations is by the Chinese remainder theorem (CRT).

The CRT theorem states that the solution of such system exists if = j.

( ffj

Proof: Let m = mr, then —, m, = 1. Let R{m,) represents the

к mi

reduced residue modulo m, which contains set of all elements relatively prime to mr Therefore, Уд e 3x 6 R(m,): ax = modm„ which

yyi

implies, 3b; e R(ntj):--bt = hnodtrii. Let x0 be the one solution, then

ntj

( r

r I YYl ffl I

x0 = > — b. a.mod m; because-b. ■ = a.modmr

mi) {mi)

If p is an odd prime and a is an integer relatively prime to p then is “д” a perfect square modulo p? Finding quadratic residues provides the answer to this question. If m is a positive integer, we say integer “д” is a quadratic residue of m if gcd(a, m) = 1 and the congruence x2 = amodm has a solution. If x1 = amodm has no solution then “a” is a quadratic non-residue of m [2], [3].

Example: Determine which integers are quadratic residues of 11.

• • Step 1: Since m = 11 is a prime number then {1,2,... 10} are relatively prime to m.
• • Step 2: Compute the squares of integers {1,2,.. .10}: l2 = 102 = Imodl 1, 22- 92 =4modl 1,32 = 82 =9modl 1,42 =72 =5mod 1,52 =62 =3mod 1.
• • Quadratic residues: 1,3,4, 5, 9, Quadratic non-residues: 2, 6, 7,8,10. Conclusion: Given any fixed positive integer m, it is possible to determine

the quadratic residue by simply listing the positive integers less than and prime to m, squaring them and reducing modm.

Lemma: If p is an odd prime and a is an integer relatively prime to p then the congruence x1 = amodm has either no solution or exactly two incon- gruent solutions modulo p.

Proof: If x1 = amodp has a solution, say x = x,h then we can easily demonstrate that x = -x0 is the second incongruent solution because (-x0)2 = x02 = amodp. Note: x0£-x0modp (2x0 =0modp, which is impossible because px0).

Now we have to show that there are no more than two incongruent solutions. Assume x = x0 and x = xt are both solutions of x2 = amodp. x01 - amodp and x2 - amodp then x02 - X]2 = 0 modp. (x0 + X])(x0 - Xi) = 0 modp i.e. p |(x0 + xj or p |(x0 - Xj). Xj - -x0modp or Xj - x0modp.

Theorem: If p is an odd prime then there are exactly ——- quadratic resi-

p — l 2

dues of p and — quadratic non-residues of p.

Proof: Consider all the squares of integers (1,2,... p-l). We know x[1] - (p-x)[1] = amodp. Let 1 < b < p-1. {p-b)[1] = b[4]modp.

Since l[4] = (p-l)[4] modp and similarly the same relation can be set among other elements of equation (1.6). Therefore, l[4], 2[4],..., f j are all distinct.

## Euler’s criterion

Euler’s criterion tells us precisely when an integer a is a quadratic residue modulo an odd prime p. Let p be odd prime and gcd(a, p) = 1. Then a is a quadratic

td

residue modulo p if and only if a [4] = lmodp

£-1 £-1

Proof: Let a be the quadratic residue then x[1] = amodp. (x[4]) [4] = a [4] modp.

£-1 M

xp~[1] = a [4] modp. By Fermat’s little theorem, x’’~' = lmodp, therefore, a [4] = lmodp.

Conversely: Given a [4] = lmodp. To prove: “я” is a quadratic residue modulo an odd prime p.

Proof: We know that there exists a primitive root g modulo p, such that any integer in Zp can be expressed as g'modp, 1 and g"' = lmodp holds only when p-lm (m = 0 or p-1). For some 1 < i < p-1 we have

,(£zi) £zi

a = g'modp. gy 2 1 = a [4] = lmodp (Given). By the property of primitive

root p-1 I if ^2 ^ j; therefore, i must be even say, i = 2/ which implies

a = g[4]’modp, a = (g')[4]modp. Hence, a is a quadratic residue modulo an odd prime p.

# Legendre Symbol

It is a convenient notation to indicate whether an integer a is a quadratic residue modulo an odd prime p. Legendre symbol of amodp is denoted as — . Formally, it is defined as:

-*(fb (§)-ЧтН(£Ь(шЬ

If p divide a with remainder, i.e. a = qp + r then — = — • Bv Euler’s crite-

м PJ P)

rion, a 1 = — modp.

P ;

The law of quadratic reciprocity relates the two Legendre symbols — and

• (a Ы
• — where p and q are odd primes:
• P)

Where ^ ^ is even when p = l(woJ4) and odd when p = 3(mod4). Consequently,

^2 2 *S CVen ^ P = l(wo^4) or q = l(mod4), while 's oc^ ^

p = q = 3[mod4). Hence,

/ /

Since the onlv possible values of — and — are ±1. Therefore,

4) v P ,

## Jacobi symbol

The Jacobi symbol is the generalization of the Legendre symbol and is formally defined as follows:

Ler n be a positive integer with prime factorization n = p['p4 ■■■pm and let

a be a positive integer relatively prime to n. Then the Jacobi symbol — is defined by: ^ n '

The above discussion regarding number theory concepts is an essential prerequisite for understanding the cryptographic algorithms [4], [5].

• [1] if a is a non-zero quadratic residue modulo p— =. -1, if a is a non —zero quadratic non-residue modulo p (1.7)
• [2] if a is a non-zero quadratic residue modulo p— =. -1, if a is a non —zero quadratic non-residue modulo p (1.7)
• [3] if a is a non-zero quadratic residue modulo p— =. -1, if a is a non —zero quadratic non-residue modulo p (1.7)
• [4] P 0, if pa
• [5] P 0, if pa
• [6] P 0, if pa
• [7] P 0, if pa
• [8] P 0, if pa
• [9] P 0, if pa
• [10] if a is a non-zero quadratic residue modulo p— =. -1, if a is a non —zero quadratic non-residue modulo p (1.7)
• [11] P 0, if pa
• [12] P 0, if pa
• [13] P 0, if pa
• [14] if a is a non-zero quadratic residue modulo p— =. -1, if a is a non —zero quadratic non-residue modulo p (1.7)
• [15] P 0, if pa
• [16] P 0, if pa
• [17] P 0, if pa
• [18] P 0, if pa
• [19] P 0, if pa
• [20] P 0, if pa