March 8, 2018 - Shawn Zhong

Math 541 – 3/7

$Lagrange s Theorem • If G is finite group, and H≤G, then |G|=|H|⋅[G:H] • In particular, ├ |H|┤|├ |G|┤ Corollary 26 • Statement ○ If G is a group, and |G| is prime ○ Then G is cyclic, hence, G≅Z\/pZ • Proof ○ If g∈G, then |g|=|⟨g⟩| ○ By Lagrange s Theorem, ├ |g|┤|├ |G|┤ ○ Thus, |g|∈{1,|G|} ○ It follow, that if g∈G∖\{1}, then |g|=|G| ○ Therefore ⟨g⟩=G ○ i.e. G is cyclic • Groups of small order Order Property 2 Cyclic 3 Cyclic 4 Cyclic or Z\/2Z×Z\/2Z 5 Cyclic 6 Cyclic or S_3 Corollary 27 • Statement ○ If G is a finite group, and g∈G, then g^|G| =1 • Proof ○ ├ |g|=|⟨g⟩|┤|├ |G|┤ ○ Thus, g^|G| =^|g|m for some integer m ○ It follows that g^|G| =1 Corollary 28 • Statement ○ If G is a finite cyclic group, then there is a bijection ○ {positive divisors of |G|}⟷{subgroups of G} • Proof ○ The map from left to right sends a divisor m of |G| to ○ the unique subgroup G with order m ○ The map from right to left sends a subgroup H to |H| Proposition 29 • Definition ○ Let G be a group and H,K≤G ○ Define HK≔{hk│h∈H,k∈K} • Statement ○ If H,K are finite subgroups of a group G, then |HK|=(|H|⋅|K|)/|H∩K| • Proof ○ HK=⋃8_(hH)▒h� ○ In the proof of Lagrange s Theorem, we showed |h�|=|K| ○ Want to show that there are (|H|⋅|K|)/|H∩K| cosets of the form hK, h∈H ○ Let h1,h2∈H ○ h1 K=h2 K ○ ⟺h2^(−1) h1∈K ○ ⟺h2^(−1) h1∈H∩K ○ ⟺h1 (H∩K)=h2 (H∩K) ○ Thus the number of distinct cosets of the form hK,h∈H is ○ [H:H∩K]=|H|/|H∩K| by Lanrange^′ s Theorem ○ Thus HK consists of |H|/|H∩K| distinct cosets of K ○ Therefore, |HK|=(|H|⋅|K|)/|H∩K| • Note: HK is not always a subgroup ○ Let G=S_3, H=⟨(1 2)⟩, K=⟨(1 3)⟩ ○ |HK|=(|H|⋅|K|)/|H∩K| =(2×2)/1=4 ○ But |HK| is not a divisor of S_3 ○ By Lagrange s Theorem, HK is not a subgroup of S_3 Proposition 30 • Statement ○ If H,K≤G, then HK≤G iff HK=KH • Note ○ HK=KH is not equivalent to hk=kh, ∀h∈H,k∈K ○ It implies that every product hk is of the form k^′ h′ and conversely • Proof (⟹) ○ H≤HK, K≤HK⇒KH⊆HK ○ Let hk∈HK ○ Set a≔(h�)^(−1), then a∈HK ○ So, a=h′ k′ for some h′∈H,k^′∈K ○ hk=a^(−1)=(h′ k^′ )^(−1)=(k^′ )^(−1) (h′ )^(−1)∈KH ○ Thus HK⊆KH ○ Therefore HK=KH • Proof (⟸) ○ HK≠∅, since 1⋅1=1∈HK ○ Let hk,h′ k^′∈HK ○ We must show hk(h′ k^′ )^(−1)∈HK ○ hk(h′ k^′ )^(−1)=h ⏟(k(k^′ )^(−1) (h′ )^(−1) )┬(∈KH) ○ Choose h′′,k^′′ s.t. ⏟(k(k^′ )^(−1) (h′ )^(−1) )┬(∈KH)=⏟(h′′ k′′)┬(∈HK) ○ Then hk(h′ k^′ )^(−1)=⏟(h^′′ )┬(∈H) ⏟(k′′)┬(∈K)∈HK ○ Therefore HK≤G • Example ○ Let G=S_3, H=⟨(1 2)⟩, K=⟨(1 3)⟩ ○ HK={(1),(1 2),(1 3),(1 3 2)} ○ KH={(1),(1 2),(1 3),(1 2 3)} ○ Thus HK≠KH ○ Therefore HK is not a subgroup of S_3$

Math 521 – 3/7

$Theorem 3.4 • Statement (a) ○ Suppose (x_n ) ⃗=(α_(1,n),α_(2,n),…,α_(k,n) )∈Rk where n∈N, then ○ {(x_n ) ⃗ } converges to (α_1,α_2,…,α_k )⟺(lim)_(n→∞)⁡〖α_(j,n) 〗=α_j (1≤j≤k) • Proof (a) ○ Assume (x_n ) ⃗→x ⃗ § Given ε 0, there exists N∈N s.t. |(x_n ) ⃗−x ⃗ | ε for n≥N § Thus, |α_(j,n)−α_j |≤|(x_n ) ⃗−x ⃗ | for n≥N,1≤j≤k § Therefore lim_(n→∞)⁡〖α_(j,n) 〗=α_j for 1≤j≤k ○ Assume lim_(n→∞)⁡〖α_(j,n) 〗=α_j for 1≤j≤k § Given ε 0, there exists N∈N s.t. |α_(j,n)−α_j | ε/√k for n≥N § |(x_n ) ⃗−x ⃗ |=|√(∑_(i=1)^k▒|α_(j,n)−α_n |^2 )|=√(∑_(i=1)^k▒|α_(j,n)−α_n |^2 ) √(∑_(i=1)^k▒ε^2/k)=ε § Therefore (x_n ) ⃗→x ⃗ • Statement (b) ○ Suppose § {(x_n ) ⃗ } and {(y_n ) ⃗ } are sequences in Rk, {β_n } is a sequence in R § (x_n ) ⃗→x ⃗, (y_n ) ⃗→y ⃗, β_n→β ○ Then § (lim)_(n→∞)⁡〖(x_n ) ⃗+(y_n ) ⃗ 〗=x ⃗+y ⃗ § (lim)_(n→∞)⁡〖(x_n ) ⃗⋅(y_n ) ⃗ 〗=x ⃗⋅y ⃗ § (lim)_(n→∞)⁡〖β_n⋅(x_n ) ⃗ 〗=β⋅x ⃗ • Proof (b) ○ This follows from (a) and Theorem 3.3 (Algebraic Limit Theorem) Compact Sets • Intuition for Rk: Closed and bounded • Open cover ○ An open cover of a set E in a metric X is ○ a collection of open sets {G_α } in X s.t. E⊂⋃8_α▒G_α • Compact ○ A set K in a metric space X is compact if ○ every open cover of K has a finite subcover • Example 1 ○ Let E=(0,1), X=R ○ E is a open cover of itself, but E is not compact ○ Let G_α=(α/2,1) for α∈(0,1), then E has {G_n } as an open cover ○ We cannot take a finite collection of these G_α and still have an open cover ○ So it has no finite subcover ○ Therefore E=(0,1) is not compact • Example 2 ○ Let K=[0,1], X=R ○ Consider {G_α }∪{G_0 }∪{G_1 }, where § G_α=(α/2,1) for α∈(0,1) § G_0=(−ε,ε) § G_1=(1−ε,1+ε) for some ε 0 ○ Then {G_α }∪{G_0 }∪{G_1 } is an open cover of [0,1] ○ It has finite subcover {G_0,G_1,G_ε } where G_ε=(ε/2,1) ○ Therefore K=[0,1] is compact$

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).$

Shawn Zhong

Shawn Zhong

Math 541 – 3/7

Math 521 – 3/7

4.3 Primes and Greatest Common Divisors

4.2 Integer Representations and Algorithms

Search

WeChat Account