Number Theory Haipeng Dai haipengdai@nju.edu.cn 313 CS Building Department of Computer Science and Technology Nanjing University
Number Theory Haipeng Dai haipengdai@nju.edu.cn 313 CS Building Department of Computer Science and Technology Nanjing University
How to compute gcd(x,y) Observation:gcd(x,y)=ged(x-y,y)=gcd(x-2y,y)=.... Suppose x>y,x=ky+d where d0) r=x mod y x=y y=r return x 2
2 How to compute gcd(x,y) Observation: gcd(x,y) = gcd(x-y, y) = gcd(x-2y, y) = …. Suppose x>y, x=ky+d where d 0) r = x mod y x = y y = r return x
How to compute gcd(x,y) Euclid's Algorithm: r2←x,r1y,u2←1，V.2←0，u1←0，y1←1 //Note that this makes ru,x+vy for n=-2 and n=-1 n←0 while r140 do rn←n-2m0drn-l,9n←rm-2/Tnml, IIIn2=gm1+ni So,un-xx+Vn-2y=9nun-x+vn)+n ISo,(un-2-qnunx+(vn2-qnvn-Dyrn un←un-2-9n4n-l,Vn←Vn-2-9nyn-l n←nt1 end return gcd(a,b)=rn-2 3
3 How to compute gcd(x,y) Euclid’s Algorithm: r-2x, r-1y , u-21, v-20, u-10, v-11 //Note that this makes rn=unx+vny for n=-2 and n=-1 n0 while rn-1≠0 do rnrn-2 mod rn-1, qn rn-2 / rn-1 , // rn-2= qnrn-1 + rn; so, un-2x+vn-2y= qn(un-1x+vn-1y)+ rn; // So, (un-2-qnun-1)x+(vn-2-qnvn-1)y= rn unun-2-qnun-1, vnvn-2-qnvn-1, n n+1 end return gcd(a, b)= rn-2
Euclid's Algorithm Example Compute ged(408,595) n Un -2 408 1 0 -1 595 0 1 0 0 408 1 0 595/408 =1 remainder 187 1 1 187 -1 1 408/187=2 remainder 34 2 2 34 3 -2 187/34 5 remainder 17 3 5 17 -16 11 34/17 =2 remainder 0 4 2 0 35 -24 Hence gcd(408,595)=r3=17=-16×408+11×595 4
4 Euclid’s Algorithm Example Compute gcd(408, 595) 595/408 = 1 remainder 187 408/187 = 2 remainder 34 187/34 = 5 remainder 17 34/17 = 2 remainder 0 Hence gcd(408, 595)= r3=17=-16×408+11×595 n qn rn un vn -2 408 1 0 -1 595 0 1 0 0 408 1 0 4 2 0 35 -24 3 5 17 -16 11 2 2 34 3 -2 1 1 187 -1 1
Finding Multiplicative Inverses Compute the multiplicative inverse al mod n It is equivalent to find a number u such that ua 1 mod n In other words,there is an integer y such that ua vn=1 Using Euclid's algorithm,we can compute ged(a,n)to find a and v such that ua vn 1 Fact:a and n are relatively prime iff there are integers u and v such that ua vn=1. Proof:If ged(a,n)=1,then we can find u and v such that ua vn=1 according to Euclid's algorithm.If gcd(a,n)=m>1,suppose a=km,n=k'm,then for any integers u and v,ua+yn ukm+vk'm=(uk+vk)mt1. 5
5 Finding Multiplicative Inverses Compute the multiplicative inverse a-1 mod n It is equivalent to find a number u such that ua = 1 mod n In other words, there is an integer v such that ua + vn = 1 Using Euclid’s algorithm, we can compute gcd(a, n) to find u and v such that ua + vn = 1 Fact: a and n are relatively prime iff there are integers u and v such that ua + vn=1. Proof: If gcd(a,n)=1, then we can find u and v such that ua + vn = 1 according to Euclid’s algorithm. If gcd(a, n)=m>1, suppose a=km, n=k’m, then for any integers u and v, ua+vn = ukm+vk’m=(uk+vk’)m≠1
Group A group,denoted by (G,),is a set G with a binary operation GXG>G such that -Associativity:a(boc)=(ab)oc(associative) -Existence of identity:there exists e Gs.t.VxeG,ex=x oe =x(identity) -Existence of inverse:for any x e G,there exists y Gs.t.x y=yox=e (inverse) ·A group(G,)is commutative if Vx,.y∈G,xoy=yo X. Examples:(Z,+),(2,+),(Q{0},×),(R,+),(R{0}, X) 6
6 Group A group, denoted by (G, ◦), is a set G with a binary operation ◦: G×GG such that ─ Associativity: a ◦ (b ◦ c) = (a ◦ b) ◦ c (associative) ─ Existence of identity: there exists e ∈ G s.t. ∀x ∈ G, e ◦ x = x ◦ e = x (identity) ─ Existence of inverse: for any x ∈ G, there exists y ∈ G s.t. x ◦ y = y ◦ x = e (inverse) A group (G, ◦) is commutative if ∀x, y ∈ G, x ◦ y = y ◦ x. Examples: (Z, +), (Q, +), (Q\{0}, ×), (R, +), (R\{0}, ×)
Integers modulo n (1/2) Letn≥2 be an integer Definition: a is congruent to b modulo n,denoted as a b mod n, if n(a-b),i.e.,a and b have the same remainder when divided by n Definition: [al {all integers congruent to a modulo n) [al,is called a residue class modulo n,and a is a representative of that class. 7
7 Integers modulo n (1/2) Let n ≥ 2 be an integer Definition: a is congruent to b modulo n, denoted as a ≡ b mod n, if n|(a-b), i.e., a and b have the same remainder when divided by n Definition: [a]n = {all integers congruent to a modulo n} [a]n is called a residue class modulo n, and a is a representative of that class
Integers modulo n(2/2) ·[an=[b]if and only if a≡b mod n There are exactly n residue classes modulo n: [0],[1],[2],..,[n-1]. "Ifx∈[a]andy∈[b],thenx+y∈[a+b]and xy∈[ab] Addition and multiplication for residue classes: [a+[b]=[a+b] [a[b]=[ab] 8
8 Integers modulo n (2/2) [a]n = [b]n if and only if a ≡ b mod n There are exactly n residue classes modulo n: [0], [1], [2], …, [n-1]. If x ∈[a] and y ∈[b], then x+y ∈[a+b] and x·y ∈[a·b]. Addition and multiplication for residue classes: [a]+[b] = [a+b] [a]·[b] = [a·b]
Z,(1/2) Define Z={[0],[1],[2],,[n-l]}. Or,more conveniently,Z=0,1,2,...n-1). (Z,+)forms a commutative additive group -Associavitivity:for Va,b,c eZn,[a]+([b]+[c])= [a]+[b+c]=[a+b+c]=[a+b]+[c]=([a]+[b])+[c] -Existence of identity:0 is the identity element. -Existence of inverse:the inverse of a,denoted by-a,is n-a. -Communitivity:for Va,be Zn,[a]+[b][b]+[a] When doing addition/subtraction in Zn just do the regular addition/subtraction and then compute the result modulo n. -InZ10,5+9=4 9
9 Zn (1/2) Define Zn={[0], [1], [2], …, [n-1]}. Or, more conveniently, Zn={0, 1, 2, …, n-1}. (Zn,+) forms a commutative additive group ─ Associavitivity: for ∀a, b, c ∈ Zn, [a]+([b]+[c]) = [a]+[b+c]=[a+b+c]=[a+b]+[c]=([a]+[b])+[c] ─ Existence of identity: 0 is the identity element. ─ Existence of inverse: the inverse of a, denoted by –a, is n-a. ─ Communitivity: for ∀a, b∈ Zn, [a]+[b] = [b]+[a] When doing addition/subtraction in Zn, just do the regular addition/subtraction and then compute the result modulo n. ─ In Z10, 5+9=4
Z,(2/2) (Z X)is not a group,because 0-1 does not exist. Even if we exclude 0 and consider only Z=Z0), (Z,X)is not necessarily a group;some a!may not exist. For a Z exists if and only if gcd(a,n)=1 gcd(a,n)=1>there exists integers x and y s.t. ax+ny=1 a][x][n][y][1]in Z →[a[x]=[l]inZm →[a]l=[x]inZm 10
10 Zn (2/2) (Zn, ×) is not a group, because 0-1 does not exist. Even if we exclude 0 and consider only Zn + = Zn\{0}, (Zn + , ×) is not necessarily a group; some a-1 may not exist. For a ∈Zn, a-1 exists if and only if gcd(a, n)=1 gcd(a, n) = 1 ⇔ there exists integers x and y s.t. ax + ny = 1 ⇔ [a][x] + [n][y] = [1] in Zn ⇔ [a][x] = [1] in Zn ⇔ [a]-1 = [x] in Zn