Mathematics Archives - Page 25 of 60 - Shawn Zhong

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

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$

Shawn Zhong

Shawn Zhong

Mathematics

4.2 Integer Representations and Algorithms

Math 521 – 3/5

Math 521 – 3/2

Math 541 – 3/5

4.1 Divisibility and Modular Arithmetic

Search

WeChat Account