Onetone Blog

4.3 Primes and Greatest Common Divisors

Primes • Definition ○ A positive integer p greater than 1 is called prime if the only positive factors are 1 and p. ○ A positive integer that is greater than 1 and is not prime is called composite. • Example ○ The integer 7 is prime because its only positive factors are 1 and 7 ○ But 9 is composite because it is divisible by 3. The Fundamental Theorem of Arithmetic • Theorem ○ Every positive integer greater than 1 can be written uniquely as ○ a prime or as the product of two or more primes ○ where the prime factors are written in order of nondecreasing size. • Examples ○ 100=2∙2∙5∙5=2^2∙5^2 ○ 641=641 ○ 999=3∙3∙3∙37=3^3∙37 ○ 1024=2∙2∙2∙2∙2∙2∙2∙2∙2∙2=2^10 The Sieve of Erastosthenes • The Sieve of Erastosthenes can be used to find all primes not exceeding a specified positive integer. • For example, begin with the list of integers between 1 and 100. • Delete all the integers, other than 2, divisible by 2. • Delete all the integers, other than 3, divisible by 3. • Next, delete all the integers, other than 5, divisible by 5. • Next, delete all the integers, other than 7, divisible by 7. • Since all the remaining integers are not divisible by any of the previous integers, other than 1 • The primes are: {2,3,5,7,11,15,1719,23,29,31,37,41,43,47,53, 59,61,67,71,73,79,83,89, 97} • If an integer n is a composite integer, then it has a prime divisor less than or equal to √n. • To see this, note that if n=ab, then a≤√n or b≤√n. • Trial division, a very inefficient method of determining if a number n is prime, • is to try every integer i≤√n and see if n is divisible by i. Infinitude of Primes • Theorem ○ There are infinitely many primes. (Euclid) • Proof ○ Assume finitely many primes: p_1, p_2, …, p_n ○ Let q = p_1 p_2⋯p_n+1 ○ Either q is prime or by the fundamental theorem of arithmetic it is a product of primes. ○ But none of the primes p_j divides q since if p_j | q, then ○ p_j divides q−p_1 p_2⋯p_n=1 . ○ Hence, there is a prime not on the list p_1, p_2, …, p_n. ○ It is either q, or if q is composite, it is a prime factor of q. ○ This contradicts the assumption that p_1, p_2, …, p_n are all the primes. ○ Consequently, there are infinitely many primes. Mersene Primes • Prime numbers of the form 2^p−1 , where p is prime, are called Mersene primes. • 2^2 − 1 = 3, 2^3 − 1 = 7, 2^5 − 1 = 37 , and 2^7 − 1 = 127 are Mersene primes. • 2^11 − 1 = 2047 is not a Mersene prime since 2047 = 23∙89. • There is an efficient test for determining if 2^p − 1 is prime. • The largest known prime numbers are Mersene primes. • As of mid-2011, 47 Mersene primes were known, the largest is 2^43,112,609 − 1, which has nearly 13 million decimal digits. Distribution of Primes • Mathematicians have been interested in the distribution of prime numbers among the positive integers. • In the nineteenth century, the prime number theorem was proved which gives an asymptotic estimate for the number of primes not exceeding x. • Prime Number Theorem ○ The ratio of the number of primes not exceeding x ○ and x/ln⁡x approaches 1 as x grows without bound. ○ The theorem tells us that the number of primes not exceeding x, can be approximated by x/ln⁡x . ○ The odds that a randomly selected positive integer less than n is prime are approximately (n/ln⁡n )/n =1/ln⁡n . Primes and Arithmetic Progressions • Euclid’s proof that there are infinitely many primes can be easily adapted to show that there are infinitely many primes in the following 4k+3 (k=1,2,3…) • In the 19th century G. Lejuenne Dirchlet showed that ○ every arithmetic progression ka+b, (k=1,2,3…) ○ where a and b have no common factor greater than 1 contains infinitely many primes. • Are there long arithmetic progressions made up entirely of primes? ○ 5,11, 17, 23, 29 is an arithmetic progression of five primes. ○ 199, 409, 619, 829, 1039,1249,1459,1669,1879,2089 is an arithmetic progression of ten primes. • In the 1930s, Paul Erdős conjectured that for every positive integer n greater than 1 • there is an arithmetic progression of length n made up entirely of primes. • This was proven in 2006, by Ben Green and Terrence Tau. Generating Primes • The problem of generating large primes is of both theoretical and practical interest. • We will see that finding large primes with hundreds of digits is important in cryptography. • So far, no useful closed formula that always produces primes has been found. • There is no simple function f(n) such that f(n) is prime for all positive integers n. • But f(n)= n^2−n+41 is prime for all integers 1,2,…, 40. • Because of this, we might conjecture that f(n) is prime for all positive integers n. • But f(41)=〖41〗^2 is not prime. • More generally, there is no polynomial with integer coefficients such that f(n) is prime for all positive integers n. • Fortunately, we can generate large integers which are almost certainly primes. See Chapter 7. Conjectures about Primes • Even though primes have been studied extensively for centuries, many conjectures about them are unresolved, including: • Goldbach’s Conjecture ○ Every even integer n, n 2, is the sum of two primes. ○ It has been verified by computer for all positive even integers up to 1.6 ∙1018. ○ The conjecture is believed to be true by most mathematicians. • There are infinitely many primes of the form n^2+1, where n is a positive integer. ○ But it has been shown that there are infinitely many primes of the form n^2+1 ○ where n is a positive integer or the product of at most two primes. • The Twin Prime Conjecture ○ The twin prime conjecture is that there are infinitely many pairs of twin primes. ○ Twin primes are pairs of primes that differ by 2. ○ Examples are 3 and 5, 5 and 7, 11 and 13, etc. ○ The current world’s record for twin primes (as of mid 2011) consists of numbers ○ 65,516,468,355∙〖23〗^33,333±1, which have 100,355 decimal digits. Greatest Common Divisor • Definition ○ Let a and b be integers, not both zero. ○ The largest integer d such that d | a and also d | b is calledthe greatest common divisor ○ The greatest common divisor of a and b is denoted by gcd(a,b). • What is the greatest common divisor of 24 and 36? ○ gcd(24, 36) = 12 • What is the greatest common divisor of 17 and 22? ○ gcd(17,22) = 1 • Definition ○ The integers a and b are relatively prime if their greatest common divisor is 1. ○ Example: 17 and 22 • Definition ○ The integers a_1, a_2, …, a_n are pairwise relatively prime ○ if gcd(a_i, a_j)= 1 whenever 1≤ i j≤n. • Determine whether the integers 10, 17 and 21 are pairwise relatively prime. ○ Because gcd(10,17) = 1, gcd(10,21) = 1, and gcd(17,21) = 1 ○ 10, 17, and 21 are pairwise relatively prime. • Determine whether the integers 10, 19, and 24 are pairwise relatively prime. ○ Because gcd(10,24) = 2, 10, 19, and 24 are not pairwise relatively prime. Finding the Greatest Common Divisor Using Prime Factorizations • Suppose the prime factorizations of a and b are: ○ a=p_1^(a_1 ) p_2^(a_2 )⋯p_n^(a_n ), b=p_1^(b_1 ) p_2^(b_2 )⋯p_n^(b_n ) ○ where each exponent is a nonnegative integer ○ and where all primes occurring in either prime factorization are included in both. • Then: ○ gcd⁡〖(a,b)=p_1^min⁡(a_1,b_1 ) p_2^min⁡(a_2,b_2 ) ⋯p_n^min⁡(a_n,b_n ) 〗 • This formula is valid since the integer on the right (of the equals sign) divides both a and b. • No larger integer can divide both a and b. • Example ○ 120 = 23 ∙3 ∙5 ○ 500 = 22 ∙53 ○ gcd(120,500) = 2^min⁡(3,2) ⋅3^min⁡(1,0) ⋅5^min⁡(1,3) = 2^2∙3^0∙5^1=20 • Finding the gcd of two positive integers using their prime factorizations is not efficient • because there is no efficient algorithm for finding the prime factorization of a positive integer. Least Common Multiple • Definition ○ The least common multiple of the positive integers a and b is ○ the smallest positive integer that is divisible by both a and b. It is denoted by lcm(a,b). • The least common multiple can also be computed from the prime factorizations. ○ lcm⁡〖(a,b)=p_1^max⁡(a_1,b_1 ) p_2^max⁡(a_2,b_2 ) ⋯p_n^max⁡(a_n,b_n ) 〗 • This number is divided by both a and b and no smaller number is divided by a and b. • Example ○ lcm(2^3 3^5 7^2, 2^4 3^3) = 2^max⁡(3,4) ⋅3^max⁡(5,3) ⋅7^max⁡(2,0) =2^4⋅3^5⋅7^2 • The greatest common divisor and the least common multiple of two integers are related by: • Theorem 5 ○ Let a and b be positive integers. ○ Then ab=gcd(a,b)∙lcm(a,b) Euclidean Algorithm • The Euclidian algorithm is an efficient method for computing the greatest common divisor of two integers. • It is based on the idea that gcd(a,b) is equal to gcd(a,c) • when a b and c is the remainder when a is divided by b. • Find gcd(91, 287): ○ 287 = 91 ∙ 3 + 14 ○ 91 = 14 ∙ 6 + 7 ○ 14 = 7 ∙ 2 + 0 ○ gcd(287, 91) = gcd(91, 14) = gcd(14, 7) = 7 • The Euclidean algorithm expressed in pseudocode is ○ In Section 5.3, we’ll see that the time complexity of the algorithm is O(log b), where a b. Correctness of Euclidean Algorithm • Lemma 1: Let a=bq+r, where a, b, q, and r are integers. Then gcd(a,b) = gcd(b,r). ○ Suppose that d divides both a and b. ○ Then d also divides a−bq=r ○ Hence, any common divisor of a and b must also be any common divisor of b and r. ○ Suppose that d divides both b and r. ○ Then d also divides bq+r=a. ○ Hence, any common divisor of a and b must also be a common divisor of b and r. ○ Therefore, gcd(a,b) = gcd(b,r). • Proof ○ Suppose that a and b are positive integers with a≥b. ○ Let r_0 = a and r_1 = b. ○ Successive applications of the division algorithm yields: § r_0=r_1 q_1+r_2, 0≤r_2 r_1 § r_1=r_2 q_2+r_3, 0≤r_3 r_2 § ⋮ § r_(n−2)=r_(n−1) q_(n−1)+r_2, 0≤r_n r_(n−1) § r_(n−1)=r_n q_n ○ Eventually, a remainder of zero occurs in the sequence of terms: a=r_0 r_1 r_2 …≥0. ○ The sequence can’t contain more than a terms. ○ By Lemma 1 , gcd(a,b) = gcd(r_0,r_1) = ∙ ∙ ∙ = gcd(r_(n−1),r_n) = gcd(r_n , 0) = r_n. ○ Hence the greatest common divisor is the last nonzero remainder in the sequence of divisions gcds as Linear Combinations • Bézout’s Theorem ○ If a and b are positive integers, then there exist integers s and t such that gcd(a,b) = sa + tb. • Definition ○ If a and b are positive integers, then ○ integers s and t such that gcd(a,b) = sa + tb are called Bézout coefficients of a and b. ○ The equation gcd(a,b) = sa + tb is called Bézout’s identity. ○ By Bézout’s Theorem, the gcd of integers a and b can be expressed in the form ○ sa + tb where s and t are integers. ○ This is a linear combination with integer coefficients of a and b. • Example ○ gcd(6,14) = (−2)∙6 + 1∙14 Finding gcds as Linear Combinations • Express gcd(252,198) = 18 as a linear combination of 252 and 198. • First use the Euclidean algorithm to show gcd(252,198) = 18 ○ 252 = 1∙198 + 54 ○ 198 = 3 ∙54 + 36 ○ 54 = 1 ∙36 + 18 ○ 36 = 2 ∙18 • Now working backwards ○ 18 = 54 − 1 ∙36 ○ 36 = 198 − 3 ∙54 • Substituting the 2nd equation into the 1st yields: ○ 18 = 54 − 1 ∙(198 − 3 ∙54 )= 4 ∙54 − 1 ∙198 • Substituting 54 = 252 − 1 ∙198 (from 1)) yields: ○ 18 = 4 ∙(252 − 1 ∙198) − 1 ∙198 = 4 ∙252 − 5 ∙198 • This method illustrated above is a two pass method. • It first uses the Euclidian algorithm to find the gcd and then • works backwards to express the gcd as a linear combination of the original two integers. • A one pass method, called the extended Euclidean algorithm, is developed in the exercises. Consequences of Bézout’s Theorem • Lemma 2: If a, b, and c are positive integers such that gcd(a, b) = 1 and a | bc, then a | c. ○ Assume gcd(a, b) = 1 and a | bc ○ Since gcd(a, b) = 1, by Bézout’s Theorem there are integers s and t such that § sa+tb=1 ○ Multiplying both sides of the equation by c, yields sac+tbc=c. ○ From Theorem 1 of Section 4.1: § a | tbc (part 2) § and a divides sac+tbc since a | sac and a | tbc (part 1) ○ We conclude a | c, since sac+tbc=c. • Lemma 3: If p is prime and p | a_1 a_2∙∙∙a_n, then ├ p┤|├ a_i ┤ for some i. • Lemma 3 is crucial in the proof of the uniqueness of prime factorizations. ○ If ├ p┤|├ a_1 a_2…a_n ┤ and p does not divide a_1 then gcd⁡〖(a_1,p)=1〗, so ├ p┤|├ a_2…a_n ┤ ○ If ├ p┤|├ a_2…a_n ┤ and p does not divide a_2 then gcd⁡〖(a_2,p)=1〗, so ├ p┤|├ a_3…a_n ┤ ○ ⋮ ○ Either this process stops because some ├ p┤|├ a_i ┤ for some i n or p|a_n Uniqueness of Prime Factorization • A prime factorization of a positive integer where the primes are in nondecreasing order is unique. ○ This part of the fundamental theorem of arithmetic. ○ Every positive integer has a prime factorization into primes, will be proved in Section 5.2. • Proof: (by contradiction) ○ Suppose that the positive integer n can be written as a product of primes in two distinct ways § n=p_1 p_2…p_s and n=q_1 q_2…q_t ○ Remove all common primes from the factorizations to get § n=p_(i_1 ) p_(i_2 )…p_(i_u ) and n=q_(j_1 ) q_(j_2 )…q_(j_v ) ○ By Lemma 3, it follows that p_(i_1 ) divides q_(j_k ), for some k ○ contradicting the assumption that p_(i_1 ) and q_(j_k ) are distinct primes. ○ Hence, there can be at most one factorization of n into primes in nondecreasing order. Dividing Congruences by an Integer • Dividing both sides of a valid congruence by an integer does not always produce a valid congruence • But dividing by an integer relatively prime to the modulus does produce a valid congruence: • Theorem 7 ○ Let m be a positive integer and let a, b, and c be integers. ○ If ac≡bc (mod m) and gcd(c,m) = 1, then a≡b (mod m). • Proof ○ Since ac≡bc (mod m), m | (ac−bc)=c(a−b) by Lemma 2 and gcd(c,m) = 1 ○ It follows that m | (a−b). Hence, a≡b (mod m).

4.2 Integer Representations and Algorithms

$Representations of Integers • In the modern world, we use decimal, or base 10, notation to represent integers. • For example when we write 965, we mean 9∙102 + 6∙101 + 5∙100 . • We can represent numbers using any base b, where b is a positive integer greater than 1. • The bases b = 2 (binary), b = 8 (octal), and b= 16 (hexadecimal) are important for computing and communications • The ancient Mayans used base 20 and the ancient Babylonians used base 60. Base b Representations • We can use positive integer b greater than 1 as a base, because of this theorem: • Theorem 1 ○ Let b be a positive integer greater than 1. ○ Then if n is a positive integer, it can be expressed uniquely in the form: ○ n=a_k b^k+a_(k−1) b^(k−1)+…+a_1 b+a_0 ○ where k is a nonnegative integer, a_0,a_1,…,a_k are nonnegative integers less than b ○ and ak≠0. The a_j (j=0,…,k) are called the base-b digits of the representation. • The representation of n given in Theorem 1 is called the base b expansion of n • and is denoted by (a_k a_(k−1)…a_1 a_0 )_b. • We usually omit the subscript 10 for base 10 expansions. Binary Expansions • Most computers represent integers and do arithmetic with binary expansions of integers. • In these expansions, the only digits used are 0 and 1. • What is the decimal expansion of the integer that has (1 0101 1111)_2 as its binary expansion? ○ (1 0101 1111)_2 = 1∙2^8 + 0∙2^7 + 1∙2^6 + 0∙2^5 + 1⋅2^4 + 1∙2^3 + 1∙2^2 + 1∙2^1 + 1 = 351 • What is the decimal expansion of the integer that has (11011)2 as its binary expansion? ○ (11011)_2 = 1 ∙2^4 + 1∙2^3 + 0∙2^2 + 1∙2^1 + 1 = 27 Octal Expansions • The octal expansion (base 8) uses the digits {0,1,2,3,4,5,6,7}. • What is the decimal expansion of the number with octal expansion (7016)_8 ? ○ 7∙8^3 + 0∙8^2 + 1∙8^1 + 6 =3598 • What is the decimal expansion of the number with octal expansion (111)_8 ? ○ 1∙8^2 + 1∙8^1 + 1 = 64 + 8 + 1 = 73 Hexadecimal Expansions • The hexadecimal expansion needs 16 digits, but our decimal system provides only 10. • So letters are used for the additional symbols. • The hexadecimal system uses the digits {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. • The letters A through F represent the decimal numbers 10 through 15. • What is the decimal expansion of the number with hexadecimal expansion (2AE0B)_16 ? ○ 2∙〖16〗^4 + 10∙〖16〗^3 + 14∙〖16〗^2 + 0∙〖16〗^1 + 11 =175627 What is the decimal expansion of the number with hexadecimal expansion (E5)_16 ? ○ 14∙〖16〗^1 + 5 = 224 + 5 = 229 Base Conversion • To construct the base b expansion of an integer n: • Divide n by b to obtain a quotient and remainder. ○ n=bq_0+a_0, 0≤a_0 b • The remainder, a_0 , is the rightmost digit in the base b expansion of n. Next, divide q_0 by b. ○ q_0=bq_1+a_1, 0≤a_1 b • The remainder, a_1, is the second digit from the right in the base b expansion of n. • Continue by successively dividing the quotients by b • obtaining the additional base b digits as the remainder. • The process terminates when the quotient is 0. • Algorithm ○ q represents the quotient obtained by successive divisions by b, starting with q = n. ○ The digits in the base b expansion are the remainders of the division given by q mod b. ○ The algorithm terminates when q = 0 is reached. • Find the octal expansion of (12345)_10 ○ Successively dividing by 8 gives: ○ 12345 = 8 ∙ 1543 + 1 ○ 1543 = 8 ∙ 192 + 7 ○ 192 = 8 ∙ 24 + 0 ○ 24 = 8 ∙ 3 + 0 ○ 3 = 8 ∙ 0 + 3 ○ The remainders are the digits from right to left yielding (30071)_8. Comparison of Hexadecimal, Octal, and Binary Representations • Each octal digit corresponds to a block of 3 binary digits. • Each hexadecimal digit corresponds to a block of 4 binary digits. • So, conversion between binary, octal, and hexadecimal is easy. Conversion Between Binary, Octal, and Hexadecimal Expansions • Find the octal and hexadecimal expansions of (11 1110 1011 1100)_2. • To convert to octal, we group the digits into blocks of three • (011 111 010 111 100)_2, adding initial 0s as needed. • The blocks from left to right correspond to the digits 3,7,2,7, and 4. • Hence, the solution is (37274)_8. • To convert to hexadecimal, we group the digits into blocks of four • (0011 1110 1011 1100)_2, adding initial 0s as needed. • The blocks from left to right correspond to the digits 3,E,B, and C. • Hence, the solution is (3EBC)_16. Binary Addition of Integers • Algorithms for performing operations with integers using their binary expansions are important as computer chips work with binary numbers. Each digit is called a bit. • The number of additions of bits used by the algorithm to add two n-bit integers is O(n).$

Math 521 – 3/5

$Theorem 3.3 (Algebraic Limit Theorem) • Suppose {s_n },{t_n } are complex sequence, and lim_(n→∞)⁡〖s_n 〗=s,lim_(n→∞)⁡〖t_n 〗=t, then • (lim)_(n→∞)⁡〖s_n+t_n 〗=s+t ○ Given ε 0 § lim_(n→∞)⁡〖s_n 〗=s⇒∃N_1∈N s.t. |s_n−s| ε/2 for n≥N_1 § lim_(n→∞)⁡〖t_n 〗=t⇒∃N_2∈N s.t. |t_n−t| ε/2 for n≥N_2 ○ Let N=max⁡(N_1,N_2 ), then for n≥N § |s_n+t_n−(s+t)|=|(s_n−s)+(t_n−t)|≤|s_n−s|+|t_n−t| ε ○ Therefore lim_(n→∞)⁡〖s_n+t_n 〗=s+t • (lim)_(n→∞)⁡〖c+s_n 〗=c+s, ∀c∈ℂ ○ Given ε 0 ○ lim_(n→∞)⁡〖s_n 〗=s⇒∃N∈N s.t.|s_n−s| ε for n≥N ○ So, |c+s_n−(c+s)|=|s_n−s| ε ○ Therefore lim_(n→∞)⁡〖c+s_n 〗=c+s • (lim)_(n→∞)⁡〖cs_n 〗=cs, ∀c∈ℂ ○ Given ε 0 ○ If c=0 § |cs_n−cs|=0 ε ○ If c≠0 § lim_(n→∞)⁡〖s_n 〗=s⇒∃N∈N s.t. |s_n−s| ε/|c| for n≥N § So |cs_n−cs|=|c||s_n−s| |c| ε/|c| =ε ○ Therefore lim_(n→∞)⁡〖cs_n 〗=cs • (lim)_(n→∞)⁡〖s_n t_n 〗=st ○ Standard approach § s_n t_n−st=s_n t_n−st_n+st_n−st=t_n (s_n−s)+s(t_n−t) ○ Rudin s approach § s_n t_n−st=(s_n−s)(t_n−t)+t(s_n−s)+s(t_n−t) ○ Given ε 0 § ∃N_1∈N s.t. |s_n−s| √ε for n≥N_1 § ∃N_2∈N s.t. |t_n−t| √ε for n≥N_2 ○ Let N=max⁡(N_1,N_2 ),then § |(s_n−s)(t_n−t)| ε for n≥N § ⇒lim_(n→∞)⁡(s_n−s)(t_n−t)=0 ○ lim_(n→∞)⁡〖s_n t_n 〗 § =lim_(n→∞)⁡[(s_n−s)(t_n−t)+t(s_n−s)+s(t_n−t)+st] § =lim_(n→∞)⁡(s_n−s)(t_n−t)+t lim_(n→∞)⁡(s_n−s)+s lim_(n→∞)⁡(t_n−t)+st § =0+0+0+st § =st ○ Therefore lim_(n→∞)⁡〖s_n t_n 〗=st • (lim)_(n→∞)⁡〖1/s_n 〗=1/s (s_n≠0, ∀n∈N and s≠0) ○ lim_(n→∞)⁡〖s_n 〗=s⇒∃N^′∈N s.t. |s_n−s| |s|/2 for n≥N^′ ○ By the Triangle Inequality, |s|−|s_n |≤|s_n−s|,∀n≥N^′ ○ ⇒|s_n |≥|s|−|s_n−s| |s|−|s|/2=|s|/2,∀n≥N^′ ○ Given ε 0, ∃N N^′ s.t. |s_n−s| 1/2 |s|^2 ε for n≥N ○ |1/s_n −1/s|=|(s−s_n)/(s_n s)| (1/2 |s|^2 ε)/(|s_n |⋅|s| ) (1/2 |s|^2 ε)/(|s|/2⋅|s| )=ε ○ Therefore lim_(n→∞)⁡〖1/s_n 〗=1/s$

Math 521 – 3/2

$Theorem 3.2 • Let {p_n } be a sequence in a metric space X • p_n→p∈X⟺ any neighborhood of p contains p_n for all but finitely many n ○ Suppose {p_n } converges to p § Let B be a neighborhood of p with radius ε § p_n→p⇒∃N∈N s.t.d(p_n,p) ε,∀n≥N § So, p_n∈B,∀n≥N § p_1,…,p_(n−1) may not be in B, but there are only finitely many of these ○ Suppose every neighborhood of p contains all but finitely many p_n § Let ε 0 be given § B≔{q∈X│d(p,q) ε} is a neighborhood of p § By assumption, all but finitely points in {p_n } are in B § Choose N∈N s.t. N i,∀p_i∉B § Then d(p_n,p) ε,∀n≥N § So, lim_(n→∞)⁡〖p_n 〗=p • Given p∈X and p^′∈X. If {p_n } converges to p and to p′, then p=p^′ ○ Let ε 0 be given § {p_n } converges to p⇒∃N∈N s.t. d(p_n,p) ε/2,∀n≥N_1 § {p_n } converges to p^′⇒∃N^′∈N s.t. d(p_n,p^′ ) ε/2,∀n≥N_2 ○ Let N=max⁡(N_1,n_2 ), then § d(p,p^′ )≤d(p_n,p)+d(p_n,p^′ ) ε/2+ε/2=ε,∀n≥N ○ Since ε 0 is arbitrary, d(p,p^′ )=0 ○ Therefore p=p^′ • If {p_n } converges, then {p_n } is bounded ○ Since {p_n } converges to some p ○ Let ε=1, then ∃N∈N s.t. d(p_n,p) 1 ○ Let q=max⁡(1,d(p_1,p),d(p_2,p),…,d(p_(N−1),p)) ○ Then d(p,p_n ) q,∀n∈N ○ By definition, {p_n } is bounded • If E⊂X, and p∈E^′, then there exists a sequence {p_n } in E s.t.p_n→p ○ Since p is a limit point of E ○ Every neighborhood of p contains q≠p, and q∈E ○ Consequently, ∀n∈N, ∃p_n∈E s.t. d(p_n,p) 1/n ○ Let ε 0 be given ○ By Archimedean property, ∃N∈N s.t. 1/N ε ○ So for n≥N, 1/n ε⇒d(p_n,p) 1/n ε ○ Therefore p_n→p$

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]$

Shawn Zhong

Shawn Zhong

4.3 Primes and Greatest Common Divisors

4.2 Integer Representations and Algorithms

Math 521 – 3/5

Math 521 – 3/2

Math 541 – 3/5

Search

WeChat Account