2018 - Page 26 of 41 - Shawn Zhong

Math 541 – 3/5

$Proposition 24: Quotient Group • Statement ○ If G is a group, and N⊴G, then ○ the set of left costs of N, denoted as G\/N (say "G mod N") ○ is a group under the operation (g_1 N)(g_2 N)=g_1 g_2 N ○ We call this group quotient group or factor group • Proof ○ Check G\/N×G\/N→G\/N, where (g_1 N,g_2 N)↦g_1 g_2 N is well-defined § Suppose g_1 N=g_1^′ N, and g_2 N=g_2^′ N § We must show g_1 g_2 N=g_1^′ g_2^′ N § g_1 N=g_1^′ N⟺(g_1′)^(−1) g_1∈N § g_2 N=g_2^′ N⟺(g_2′)^(−1) g_2∈N § We must show that (g_1^′ g_2^′ )^(−1) g_1 g_2∈N⟺g_1 g_2 N=g_1^′ g_2^′ N § (g_1^′ g_2^′ )^(−1) g_1 g_2 § =(g_2^′ )^(−1) (g_1^′ )^(−1) g_1 g_2 § =(g_2^′ )^(−1) (g_1^′ )^(−1) g_1 [g_2^′ (g_2^′ )^(−1) ] g_2 § =(g_2^′ )^(−1) ⏟((g_1^′ )^(−1) g_1 )┬(∈N) g_2^′ ⏟((g_2^′ )^(−1) g_2 )┬(∈N) § =⏟((g_2^′ )^(−1) (g_1^′ )^(−1) g_1 g_2^′ )┬(∈N) ⏟((g_2^′ )^(−1) g_2 )┬(∈N) § Thus (g_1^′ g_2^′ )^(−1) g_1 g_2∈N § Therefore, the operation is well-defined ○ Existence of Identity § 1⋅N=N ○ Existence of Inverse § (gN)^(−1)=g^(−1) N § Since (gN)(g^(−1) N)=gg^(−1) N=N ○ Associativity § (g_1 Ng_2 N)(g_3 N) § =(g_1 g_2 N)(g_3 N) § =g_1 g_2 g_3 N § =g_1 N(g_2 g_3 N) § =g_1 N(g_2 Ng_3 N) • Note ○ If N⊴G, then there is a surjective homomorphism ○ f:G→G\/N given by g→gN ○ ker⁡f=N, since gN=N⟺g∈N ○ This shows that, if H≤G, then H⊴G iff ○ H is the kernel of a homomorphism from G to some other group • Example 1 ○ Let H be a subgroup of Z ○ H⊴Z since Z is abelian ○ Since Z is cyclic, H is also cyclic ○ So write H=⟨n⟩ ○ Then there is isomorphism § Z\/⟨n⟩→Z\/nZ § a+⟨n⟩→a ̅ • Example 2 ○ If G is a group, then {1_G }⊴G and G⊴G § G\/{1_G }≅G § G\/G≅ ∗ , where ∗ is the trivial group of order 1 ○ Intuition: The bigger the subgroup, the smaller the quotient Index • Definition ○ If G is a group, and H≤G, then ○ The index of H is the number of distinct left cosets of H in G ○ Denote the index by [G:H] • Note ○ If N⊴G, then [G:N]=|G/N| • Example ○ [Z⟨n⟩]=|ZnZ=n Theorem 25: Lagranges Theorem • Statement ○ If G is finite group, and H≤G, then |G|=|H|⋅[G:H] ○ In particular, ├ |H|┤|├ |G|┤ • Notice ○ If in the setting of Lagranges Theorem, H⊴G, then ○ |G|=|H|⋅|G/H|⇒|G/H|=|G|/|H| • Proof ○ Let n≔|H|, and k≔[G:H] ○ Let g_1,…,g_k be the representatives of the distinct cosets of H in G ○ (In other words: if g∈G, then gH∈{g_1 H,g_2 H,…,g_k H}) ○ By proposition 22, left costs are either equal or disjoint ○ So, G=g_1 H∪g_2 H∪…∪g_k H ○ Let g∈G, then there is a function f:H→gH, defined by h↦gh ○ f is certainly surjective ○ f is also injective since if gh1=gh2, then h1=h2 ○ Thus, |gH|=|H| ○ |G|=|g_1 H|+…+|g_k H|=⏟(n+n+…+n)┬(k copies)=kn ○ Therefore |G|=|H|⋅[G:H]$

4.1 Divisibility and Modular Arithmetic

$Division • Definition ○ If a and b are integers with a ≠ 0, ○ then a divides b if there exists an integer c such that b = ac. ○ When a divides b we say that a is a factor or divisor of b and that b is a multiple of a. ○ The notation a | b denotes that a divides b. ○ If a | b, then b/a is an integer. ○ If a does not divide b, we write a ∤ b. • Example ○ Determine whether 3 | 7 and whether 3 | 12. ○ 3 | 7 is false ○ 3 | 12 is true Properties of Divisibility • Theorem 1: Let a, b, and c be integers, where a ≠0. ○ If a | b and a | c, then a | (b + c); ○ If a | b, then a | bc for all integers c; ○ If a | b and b | c, then a | c. • Proof (i) ○ Suppose a | b and a | c, then it follows that ○ there are integers s and t with b = as and c = at. ○ Hence, b + c = as + at = a(s + t). ○ Hence, a | (b + c) • Corollary ○ If a, b, and c be integers, where a ≠0, such that a | b and a | c, ○ then a | mb + nc whenever m and n are integers. Division Algorithm • When an integer is divided by a positive integer, there is a quotient and a remainder. • This is traditionally called the “Division Algorithm,” but is really a theorem. • Division Algorithm ○ If a is an integer and d a positive integer, then ○ there are unique integers q and r, with 0 ≤ r d, such that ○ a = dq + r ○ d is called the divisor. ○ a is called the dividend. ○ q is called the quotient. ○ r is called the remainder. • Example: What are the quotient and reminder when 101 is divided by 11? ○ 101=11⋅9+2 ○ Thus the quotient is 9, and the remainder is 2 ○ 101 div 11 = 9 ○ 101 mod 11 = 2 • Example: What are the quotient and reminder when -11 is divided by 3? ○ −11=3⋅(−4)+1 Congruence Relation • Definition ○ If a and b are integers and m is a positive integer, ○ then a is congruent to b modulo m if m divides a – b. ○ The notation a ≡ b (mod m) says that a is congruent to b modulo m. ○ We say that a ≡ b (mod m) is a congruence and that m is its modulus. ○ Two integers are congruent mod m if and only if they have the same remainder when divided by m. ○ If a is not congruent to b modulo m, we write a ≢ b (mod m) • Determine whether 17 is congruent to 5 modulo 6 ○ 17 ≡ 5 (mod 6) because 6 divides 17 − 5 = 12. • Determine whether 24 and 14 are congruent modulo 6. ○ 24 ≢ 14 (mod 6) since 24 − 14 = 10 is not divisible by 6. The Relationship between (mod m) and mod m Notations • The use of “mod” in a ≡ b (mod m) and a mod m = b are different. ○ a ≡ b (mod m) is a relation on the set of integers. ○ In a mod m = b, the notation mod denotes a function. • The relationship between these notations is made clear in this theorem. • Theorem 3 ○ Let a and b be integers, and let m be a positive integer. ○ Then a ≡ b (mod m) if and only if ○ a mod m = b mod m. More on Congruence • Theorem 4 ○ Let m be a positive integer. ○ The integers a and b are congruent modulo m if and only if ○ there is an integer k such that a = b + km. • Proof: ○ If a ≡ b (mod m), then (by the definition of congruence) m | a – b. ○ Hence, there is an integer k such that a – b = km and equivalently a = b + km. ○ Conversely, if there is an integer k such that a = b + km, then km = a – b. ○ Hence, m | a – b and a ≡ b (mod m). Congruence of Sums and Products • Theorem 5 ○ Let m be a positive integer. ○ If a ≡ b (mod m) and c ≡ d (mod m), then § a + c ≡ b + d (mod m) § ac ≡ bd (mod m) • Proof: ○ Because a ≡ b (mod m) and c ≡ d (mod m) ○ by Theorem 4 there are integers s and t with b = a + sm and d = c + tm. ○ Therefore, § b + d = (a + sm) + (c + tm) = (a + c) + m(s + t) and § b d = (a + sm) (c + tm) = ac + m(at + cs + stm). ○ Hence, a + c ≡ b + d (mod m) and ac ≡ bd (mod m). • Example ○ Because 7 ≡ 2 (mod 5) and 11 ≡ 1 (mod 5) , it follows from Theorem 5 that ○ 18 = 7 + 11 ≡ 2 + 1 = 3 (mod 5) ○ 77 = 7 ∙ 11 ≡ 2 ∙ 1 = 2 (mod 5) Algebraic Manipulation of Congruence • Multiplying both sides of a valid congruence by an integer preserves validity. ○ If a ≡ b (mod m) holds then c∙a ≡ c∙b (mod m), where c is any integer, ○ holds by Theorem 5 with d = c. • Adding an integer to both sides of a valid congruence preserves validity. ○ If a ≡ b (mod m) holds then c + a ≡ c + b (mod m), where c is any integer, ○ holds by Theorem 5 with d = c. • Dividing a congruence by an integer does not always produce a valid congruence. ○ The congruence 14≡ 8 (mod 6) holds. ○ But dividing both sides by 2 does not produce a valid congruence since ○ 14/2 = 7 and 8/2 = 4, but 7≢4 (mod 6). Computing the mod m Function of Products and Sums • We use the following corollary to Theorem 5 to compute the remainder of the product or sum of two integers when divided by m from the remainders when each is divided by m. • Corollary: Let m be a positive integer and let a and b be integers. Then ○ (a + b) (mod m) = ((a mod m) + (b mod m)) mod m ○ ab mod m = ((a mod m) (b mod m)) mod m. Arithmetic Modulo m • Definitions ○ Let Zm be the set of nonnegative integers less than m: {0,1, …., m−1} ○ The operation +m is defined as a +_m b = (a + b) mod m. ○ This is addition modulo m. ○ The operation ∙m is defined as a ∙_m b = (a ∙ b) mod m. ○ This is multiplication modulo m. • Example: Find 7 +_11 9 and 7 ∙_11 9. ○ 7 +_11 9 = (7 + 9) mod 11 = 16 mod 11 = 5 ○ 7 ∙_11 9 = (7 ∙ 9) mod 11 = 63 mod 11 = 8 • The operations +_m and ∙_m satisfy many of the same properties as ordinary addition and multiplication. ○ Closure § If a and b belong to Zm , then a +_m b and a ∙_m b belong to Zm. ○ Associativity § If a, b, and c belong to Zm , then § (a +_m b) +_m c = a +_m (b +_m c) § (a ∙_m b) ∙_m c = a ∙_m (b ∙_m c). ○ Commutativity § If a and b belong to Zm , then § a +_m b = b +_m a § a ∙_m b = b ∙_m a. ○ Identity elements § The elements 0 and 1 are identity elements for addition and multiplication modulo m, respectively. § If a belongs to Zm , then a +_m 0 = a and a ∙_m 1 = a. ○ Additive inverses § If a≠ 0 belongs to Zm § then m − a is the additive inverse of a modulo m § and 0 is its own additive inverse. § a +_m (m− a) = 0 § 0 +_m 0 = 0 ○ Distributivity § If a, b, and c belong to Zm , then § a ∙_m (b +_m c) = (a ∙_m b) +_m (a ∙_m c) § (a +_m b) ∙_m c = (a ∙_m c) +_m (b ∙_m c). • Multiplicative inverses have not been included since they do not always exist. • For example, there is no multiplicative inverse of 2 modulo 6. • Using the terminology of abstract algebra ○ Zm with +_m is a commutative group ○ Zm with +_m and ∙_m is a commutative ring$

Math 521 – 2/28

$Convergence and Divergence • Definition ○ A sequence {p_n } in a metric space X converges to a point p∈X if ○ Given any ε 0, ∃N∈N s.t. d(p,p_n ) ε, ∀n≥N ○ If {p_n } converges to p, we write § p_n→p § lim_(n→∞)⁡〖p_n 〗=p § lim⁡〖p_n 〗=p ○ If {p_n } does not converge, it is said to diverge • Intuition ○ ε is small ○ N is a "point of no return" beyond which sequence is within ε of p Range and Bounded • Range ○ Given a sequence {p_n } ○ The set of points p_n (n∈N) is called the range of the sequence ○ Range could be infinite, but it is always at most countable ○ Since we can always construct a function f:N→{p_n }, where f(n)=p_n • Bounded ○ A sequence {p_n } is said to be bounded if its range is bounded Examples • Consider the following sequences of complex numbers {s_n } Limit Range Bounded s_n=1/n 0 Infinite Yes s_n=n^2 Divergent Infinite No s_n=1+(−1)^n/n 1 Infinite Yes s_n=i^n Divergent {±1,±i} Yes s_n=1 1 {1} Yes • Proof:lim_(n→∞)⁡〖1/n〗=0 ○ Let ε 0 ○ By Archimedean Property, we can choose N∈N s.t. N 1/ε ○ ∀n≥N, n 1/ε⇒1/n ε ○ i.e. d(1/n,0)=|1/n| ε,∀n≥N ○ Therefore lim_(n→∞)⁡〖1/n〗=0$

Math 541 – 2/28

$Coset • If G is a group, H≤G, and g∈G • Define gH≔{ghhH} • Similarly, define Hg≔{h�│hH} • gH is caleld a left coset, and Hg is called a right coset • An element of a coset is called a representative of the coset Proposition 22: Properties of Coset • Let G be a group and H≤G, then • For g_1,g_2∈G,g_1 H=g_2 H⟺g_2^(−1) g_1∈H ○ (⟹) Choose h∈H s.t. g_1=g_2 h (since g_1=g_1⋅1∈g_1 H=g_2 H) ○ Therefore g_2^(−1) g_1=h∈H ○ (⟸) Choose h∈H s.t. g_1=g_2 h ○ ∀h′∈H, g_1 h′=g_2 ⏟(h^′ )┬(∈H)∈g_2 H⇒g_1 H⊆g_2 H ○ ∀h′∈H,g_2 h′=g_1 ⏟(h(−1) h′ )┬(∈H)∈g_1 H⇒g_2 H⊆g_1 H ○ Therefore g_1 H=g_2 H • The relation ~ on G given by g_1~g_2 iff g_1∈g_2 H is a equivlance relation ○ Reflexive § If g∈G, then g=g⋅1∈gH § So g~g ○ Symmetric § If g_1,g_2∈G, and g_1~g_2 i.e. g_1∈g_2 H, then § g_1=g_2 h for some h∈H § Thus g_1 h(−1)=g_2 § So g_2∈g_1 H, which means g_2~g_1 ○ Transitive § Suppose g_1~g_2 and g_2~g_3 § This means g_1∈g_2 H and g_2∈g_3 H § Choose h1,h2∈H s.t. g_1=g_2 h, and g_2=g_3 h § Then g_1=g_3 h2 h1∈g_3 H § So g_1~g_2 • In particular, left/right cosets are either equal or disjoint ○ Suppose g_1,g_2∈G, and z∈g_1 H∩g_2 H ○ Suppose x∈g_1 H, then x~g_1~z~g_2 ○ So x∈g_2 H ○ This implies that g_1 H⊆g_2 H ○ To get g_2 H⊆g_1 H, exchange the roles of g_1 and g_2 ○ Therefore g_1 H=g_2 H • Example 1 ○ Let G be a group, H≤G. If h∈H, then hH=H ○ Let h′∈H, then h′=h(h(−1) h′ )∈hH ○ Thus H⊆hH ○ By closure under the operation, hH⊆H ○ Therefore hH=H • Example 2 ○ Let G=Z\/6Z, and H= unique subgroup of Z\/6Z of order 2 ○ H={0 ̅,3 ̅ }≤Z\/6Z ○ Left cosets of H in G § 0 ̅+{0 ̅,3 ̅ }={0 ̅,3 ̅ } § 1 ̅+{0 ̅,3 ̅ }={1 ̅,4 ̅ } § 2 ̅+{0 ̅,3 ̅ }={2 ̅,5 ̅ } § 3 ̅+{0 ̅,3 ̅ }={0 ̅,3 ̅ } § 4 ̅+{0 ̅,3 ̅ }={1 ̅,4 ̅ } § 5 ̅+{0 ̅,3 ̅ }={2 ̅,5 ̅ } ○ Note § |G|=6, |H|=2, and H has 3 distinct cosets (2⋅3=6) § If G is a finite group, and H≤G, then ├ |H|┤|├ |G|┤, and § H has |G|/|H| distinct left (or right) cosets in G Normal Subgroup • Definition ○ Let G be a group, let N≤G ○ N is a normal subgroup if gng^(−1)∈N, ∀n∈N,∀g∈G ○ In other words, N is closed under conjugation ○ If N≤G is normal, we write N⊴G • Example 1 ○ If G is abelian, every subgroup of G is normal ○ Suppose H≤G ○ Let h∈H and g∈G ○ Thus ghg^(−1)=hgg^(−1)=h∈H • Example 2 ○ Let G=S_3, H=⟨(1 2)⟩ ○ Suppose g=(1 2 3), h=(1 2) ○ ghg^(−1)=(1 2 3)(1 2) (1 2 3)^(−1)=(1 2 3)(1 2)(1 3 2)=(2 3)∉H ○ Therefore H⋬G • Example 3 ○ ⟨(1 2 3)⟩ in S_3 is normal • Example 4 ○ Let G=GL_n (R ○ Let P,A∈G, then PAP^(−1) is change of basis matrix ○ Note: In GL_n (R, conjugation amounts to changing basis Proposition 23: Properties of Normal Subgroup • Statement ○ Let N be a subgroup of a group G ○ N⊴G iff gN=Ng,∀g∈G • Proof (⟹) ○ Suppose N⊴G ○ Let g∈G, n∈N ○ gn=gn(g^(−1) g)=⏟(gng^(−1) )┬(∈N) g∈Ng⇒gN⊆Ng ○ ng=(gg^(−1) )ng=g ⏟(g^(−1) ng)┬(∈N)∈gN⇒Ng⊆gN ○ Therefore gN=Ng • Proof (⟸) ○ Suppose gN=Ng,∀g∈G ○ Let g∈G,n∈N ○ We must show gng^(−1)∈N ○ Choose n^′∈N s.t. gn=n^′ g ○ Then gng^(−1)=n^′∈N ○ Therefore N⊴G • Example ○ Let f:G→H be a homomorphism, then ker⁡f⊴G ○ ker⁡f is a subgroup of G § ker⁡f≠∅, since f(1_G )=1_H § If k_1,k_2∈ker⁡f § f(k_1 k_2^(−1) )=f(k_1 )f(k_2 )^(−1)=1_H § Thus k_1 k_2^(−1)∈ker⁡f § Therefore ker⁡f≤G ○ ker⁡f is normal § Let g∈G,k∈ker⁡f § f(gkg^(−1) )=f(g)f(k)f(g)^(−1)=f(g)f(g)^(−1)=1_H § ⇒gkg^(−1)∈ker⁡f∎$