[PDF] IIT Kharagpur 1 Basic Properties of Integers II

View - Download IIT Kharagpur 1 Basic Properties of Integers II

Previous PDF

Next PDF

Computer Science & Engineering DepartmentIIT Kharagpur

Computational Number Theory: CS60094

Lecture III

Instructor:Goutam BiswasSpring Semester 2014-2015

1 Basic Properties of Integers II

We shall start with the definition of one of the most important binaryrelations in number theory. The notation for this relation was introduced byCarl Friedrich Gauss 1

1.1 Congruences and Modular Arithmetic

We start with the definition of the binary relationcongruence modulon.

Definition 1:

Given a positive integern, we define a binary relation onZ. Two integersaandbare said to be related ifn(a?b). We writeab(modn) and read it as "ais congruent tobmodulon". In other words,ais congruent tobmodulon, ifamodn=bmodni.e. a=pn+randb=qn+r, where 0r < n. Bothaandbleave same remainder when divided byn. So we geta?b=n(p?q) ora=b+ns, for somesZ. It is not difficult to prove thatcongruenceis an equivalence relation - for all a,b,cZ, aa(modn), ifab(modn), thenba(modn), ifab(modn) andbc(modn), thenac(modn). We know that an equivalence relation partitions the underlying set intoequiv- alence classes. Elements of each class are equivalent to one another. In case of congruence modulon, an equivalence class contains all integers that have same remainders when divided byn. Corresponding tonremainders 0,1,,n?1, there arenequivalence classes, [0],,[n?1].

Example 1.

Letn= 7, there are seven possible values of remainders 0,1,2,3,4,5,6 when any integer is divided by 7. Correspondingequivalence classes are [0],[1],[2],[3],[4],[5],[6]. No two of these classes have any common elements and their union is the set of integers. Following is an example of an equivalence class. = [?17] = [?10] = [?3] = [4] = [11] ==,?17,?10,?3,4,11,. The congruence relation isconsistentorcompatiblewith the arithmetic oper- ations ofZ.

Proposition 1.

Leta,b,c,d,nZandn >1. Ifab(modn) andc

d(modn), thena+cb+d(modn) andacbd(modn). Proof:Leta=b+nsandc=d+nt, soa+c= (b+d)+nu, whereu=s+t. Similarly,ac= (b+ns)(d+nt) =bd+nv, wherev=s(d+nt) +bnt. QED. Following are a few properties of congruence wherea,b,c,dZandn,kis a positive integer.

1. Ifab(modn), thena+cb+c(modn) andacbc(modn).

2. Ifab(modn), thenakbk(modn).

3. Ifacbc(modn), thenab(modn

d), wheregcd(c,n) =d.

1In his bookDisquisitiones Arithmeticae, Gauss noted, "We have adopted this symbol

because of the analogy between equality and congruence. Forthe same reason Legendre, in the treatise which we shall often have occasion to cite, usedthe same sign for equality and congruence. To avoid ambiguity we have made a distinction." 1 Proof:We shall give the proof of (3) only. Letc=dcandn=dn. We know thatgcd(c,n) = 1 and (a?b)c=nkfor some integerk. Dividing both sides bydwe get (a?b)c=nk. Asgcd(c,n) = 1,n(a?b). So,ab(modn) i.e.ab(modn d).QED. There are two important corollaries: (i) Ifacbc(modn) andgcd(c,n) = 1, thenccan be cancelled from both sides i.e.ab(modn). (ii) Ifnis a prime andn c, thengcd(c,n) = 1, and againab(modn). Note that in general we cannot do this cancellation, 3532(mod 9), but 52(mod 9). The structure (Z,+,,0,1) is acommutative ring with identity, and the congruence relation is consistent with both the operations. This implies that thequotient set,Z/(modn), denoted byZ/nZorZn=[0],[1],,[n?1] (we assumen >1), also forms acommutative ring with identityunder modulo-n addition and multiplication operations. We often denote the equivalence class [m] by the least non-negative element of [m]. It is the usual remainder when any element of [m] is divided byn. In this notationZn=0,1,,n?1. But it is perfectly acceptable to take a set ofnintegersa1,a2,,an, taken one from each equivalence class, to represent Z/nZorZn. Such a set of integers is called acomplete system of residues.

Definition 2:

We define +mandn(orn) onZnas follows:

a+nb= (a+b) modn, anb= (ab)nn. Both operations are well-defined due to compatibility of '+" and '" with con- gruence. As we claimed earlier, the structure (Zn,+n,n,0,1) is a commutative ring with identity.

Proposition 2.

Let [a] be a congruence class ofZmodulo positive integern, and b[a]. Ifgcd(a,n) = 1, thengcd(b,n) = 1. Proof:So we haveax+ny= 1 anda=b+nk, for somex,y,kZ. So we have (b+nk)x+ny= 1 i.e.bx+n(kx+y) = 1. Sobis also relatively prime tonQED. We define an interesting subset ofZnin the following way.

Definition 3:

Zn=aZn:gcd(a,n) = 1. the size ofZn, is given by

theEuler"s totientfunctionφ(n), the count of integers within 0 tonthat are relatively prime ton.

Proposition 3.

Prove that (Zn,n) is an abelian group, wheren >1.

Proof:We shall show thatZnis closed undern, 1Znand ifaZn, then there isbZn, so thatanb= 1. The associativity comes free of cost. gcd(n,1) = 1, so 1Zn. Leta,bZn, so we have by the Bezout"s identity,axa+nya= 1 andbxb+ ny b= 1, wherexa,ya,xb,ybZ. Multiplying the identity we getab(xaxb) + n(xayb+yaxb+nyayb) = 1. So we havegcd(ab,n) =gcd(abmodn,n) = 1 i.e. anbZn. LetaZn, so by the Bezout"s identity we haveax+ny= 1, wherex,yZ. It is clear thatgcd(x,n) = 1. Letx=nq+b, where 0b < n. Sogcd(x,n) = gcd(b,n) = 1 i.e.bZn. Again,a(nq+b)+ny= 1 implies thatab1(modn) i.e.amb= 1. Sobis the inverse ofa. QED. Acommutative ring with identityis called afieldif every non-zero element has a multiplicative inverse. It is clear from our previous discussion thatZp=

1,,p?1ifpis a prime (gcd(p,q) = 1, 1q < p). We have already proved

thatZpis anabelian group. So for every primep, (Zp,+p,0,p,1) is afield.

1.1.1 Linear Congruence

We are now ready to solve linear congruence. We start with the following example.

Example 2.

Consider the congruence 5x+ 43(mod 7). Subtracting 4 from both sides we get, 5x ?1(mod 7). We know 531(mod 7) so we multiply our congruence by 3 and getx ?3(mod 7). So the solutions of xare those integers that belongs to the equivalence class of [4] = [?3] = ,?17,?10,?3,4,11,. 2 It is easy to verify that these are solutions of the original equation. Take x=?10,?105 + 4 =?463(mod 7). The congruence 5x ?1(mod 7) is equivalent to 5x6(mod 7). As gcd(5,7) = 1, 5Z7. So there is the inverse of 5 inZ7, which is 3. We can mul- tiply the congruence by 3 and get (35)x(36)(mod 7) i.e.x4(mod 7).

Example 3.

Now consider the congruence 3x2(mod 6). There is noxsatis- fying the congruence. From the algebraic point of view 3Z6, so there is no multiplicative inverse of it. So 3 cannot be cancelled from the left side.Another view is that the subgroup0,3of (Z6,+) does not contain 2. It is clear that all linear congruence cannot be solved. Following theorem characterises it.

Theorem 4.

Leta,nZ,n >0, andgcd(a,n) =d. For eachbZ, the

congruenceaxb(modn) has a solution, if and only ifdb. Proof:Leta=da,n=dn, wheregcd(a,n) = 1. LetbZsuch that the congruence has a solution: axb(modn) ax=b+qn,for someqZ ax?qn=b d(ax?qn) =b db. We know that there are integersα,βso thatd=aα+nβ. Ifdb, then b=kd=k(aα+nβ) =aα+nβ. Soαis a solution ofaxb(modn). QED. We know under which condition a linear congruence has a solution. Our next propositions show a few properties of the solutions.

Proposition 5.

1. If the linear congruenceaxb(modn) has a solution, then there is a

solution inZn.

2. Ifxis a solution of the linear congruenceaxb(modn), then every

integer of the formx+ni/d, whered=gcd(a,n) andiZ, is also a solution; and every solution is of this form.

3. Ifxis a solution of the linear congruenceaxb(modn) andd=

gcd(a,n), thenx+ni/d, wherei 0,,d?1are incongruent so- lutions.

4. Letd=gcd(a,n), then every solution ofaxb(modn) is congruent to

a solution of the formx+ni/d, wherei 0,,d?1.

Proof:

1. Letxbe a solution. By the division algorithmx=nq+x0, 0x0< n.

We havenk=ax?b=a(nq+x0)?b. Son(k?aq) =ax0?b, implies n(ax0?b) andx0is a solution of the congruence.

2.a(x+ni/d)ax+ani/dax+aniaxb(modn), wherea=ad.

So (x+ni/d) is a solution of the congruence.

Letybe any solution of the congruence. We haveaxay(modn). Let a=ad, sogcd(a,n) = 1, and we can cancelafrom both sides. We have dxdy(modn)dy=dx+niy=x+ni/d, whereiZ.

3. Letn=nd. Ifx+ni/dx+nj/d(modn), wherei,j 0,,d?1,

thenn(i?j)/d=n(i?j) is divisible byn. But that is not possible unless i=jas 04. Letx+nj/dbe a solution. We can writej=dq+i, where 0i < d. So x+nj/dx+n(dq+i)/dx+nq+ni/dx+ni/d(modn). 3 QED. Our final conclusion is thataxb(modn) has exactlydincongruent solu- tions whengcd(a,n) =ddividesb. The solution isunique(up to congruence) ifaandnare relatively prime i.e.aZn. The congruenceaxb(modn) has a solution whenbmodnis an element of the subgroup ofZngenerated2by amodn. In factaxb(modn) has a solution if and only ifaxb(modn) has a solution, wherea=ad,b=bdandn=nd, such thatgcd(a,n) =d. Ifgcd(a,n) = 1, the congruenceaxb(modn) may be viewed as an equa- tionax=binZn. The solution isx=a1nb. This also explains the cancellation law whengcd(a,n) = 1.axay(modn)xy(modn) is equivalent toax=ayx=yinZn.

Example 4.

The congruence 6x15(mod 21) has a three solutions 6, 13 and

20 inZ21asgcd(6,21) = 3 and 315.

The congruence can be reduced to 2x5(mod 7) which has unique solution 6 inZ7. The equation 6xb(mod 21) has a solution ifbis an element of the sub- group0,3,6,9,12,15,18ofZ21generated by 6. We define a homomorphismf:Z21Z7, xxmod 7. The Kernel off is0,7,14(elements ofZ21mapped to 0 ofZ7).Kerfis a subgroup ofZ21, which defines the following equivalence relation onZ21:ab(modKerf) if a+21(?b)Kerf. Each equivalence class has three elements. There is an isomorphismφ:ImfZ21/Kerf. The solution of 2x5(mod 7) is 6. φ(6) =6,13,20, three solutions of 6x15(mod 21). Algorithmically the solution ofaxb(modn) is simple.

1. Computegcd(a,n) =dand the Bezout"s coefficientsx,yso thatax+ny=

d.

2. Ifdb, then there is a solution.

3. Ifb=db, thena(xb) +nyb=b. Soxbmodn=x0is a solution inZn.

4. We can find all other solutions as (x0+ni/d) modn, wherei= 1,,d?1.

1.1.2 Linear Diophantine Equation of Two Variables

We consider the equationax+by=c, wherea,b,cZanda,bare non-zero. We wish to get solutions ofx,yin integers. Without any loss of generality we may takeb >0. Ifb <0 we takeb=?band solve the equationax+by=c. Any solution ofax+by=cgives a solution of the original equation.

Proposition 6.

The two variable Diophantine equationax+by=chas a solution if and only if the linear congruenceaxc(modb) has a solution, whereb >0. Proof:Ifx0,y0is a solution ofax+by=c, thenx0is a solution ofax c(modb). Ifx0is a solution ofaxc(modb), then there is a somey0Zsuch that ax

0?c=by0i.e.ax0+b(?y0) =c. So, (x0,?y0) is a solution ofax+by=c.

QED. So we conclude thatax+by=chas a solution if and only ifgcd(a,b) divides c. If (x0,y0) is a solution ofax+by=c, andgcd(a,b) =d, then (x0?bi d,y0+aid) is a solution ofax+by=c, whereiZ.

1.1.3 The Chinese Remainder Theorem

Letn1,,nkbe a set of pairwise relatively prime positive integers. Our main claim is that there is a bijection betweenZNandZn1 Znk, where

N=ki=1ni. We start with the following example.

Example 5.

Letk= 2 andn1= 3 andn2= 4. Following is a sequence of

2Afterward we shall talk about a subgroup generated by an element of a group.

4 remainders.quotesdbs_dbs14.pdfusesText_20

[PDF] a crash course in c

[PDF] a d s solutions pvt ltd bangalore

[PDF] a d s solutions pvt ltd zauba

[PDF] a dialogue between a teacher and a student about studies

[PDF] a feasible solution for

[PDF] a feasible solution to an lp problem

[PDF] a feasible solution to linear programming problem should

[PDF] a final class can be abstract

[PDF] a final class can be extended

[PDF] a final class can be extended. true false

[PDF] a final class can have subclass i.s. it can be extended

[PDF] a final method can be inherited

[PDF] a first course in graph theory pdf

[PDF] a fois b au carré

[PDF] a for apple to z for