Mathematical Division Theorems and Base Conversion Explained

Slide Note

The content covers topics such as the division algorithm, properties of divisibility, the division theorem, proofs, change of radix, and base conversion in mathematics. It delves into how integers can be divided, the relationship between divisors and multiples, and the process of converting numbers between different number systems using the division theorem. Examples and illustrations help in understanding and applying these mathematical concepts effectively.

mallonee_k Follow

Uploaded on Sep 14, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Section 4.3, 4.4, 4.5 Few slides are taken form the lecture slides of Prof. Bulatov.

The division algorithm: Prime numbers Divisibility Suppose x and y are integers with x 0, we say that x divides y , or y is divisible by x , and write x|y, if there is an integer z such that y=zx. We also say x is a divisor of y and y is a multiple of x. 3 | 12 9|0 -3|-12 note that sign never makes a difference: if x|y, x|-y, -x|y, - x|-y 3|12

More Properties of | All variables range over integers. if x|y and y|x, either x=y or x=-y. If x|y and y|z, then x|z. If x|y, x|yz. if x=x+z and w divides two of x, y and z, it divides the third. if x|y and x|z, the x|(ay + bz)

The Division Theorem If a and b are integers (elements of Z) with b > 0, then there exist unique integers q and r such that a = qb +r with 0 r < b. We call q the quotient and r the remainder. If a=38 and b=7, then q=5 and r=3. If a=14 and b=1, then q=14 and r=0 If a= - 20 and b=5, then q=-4 and r=0 If a= - 9 and b= 4, then q=-3 and r=3 If a= - 9 and b= - 4, then the Theorem doesn t apply.

Proof of the Division Theorem Part I: Existence If b divides a, a=b.z and we take q=z and r=0. If a < b, a = 0.b + a, we take q=0 and r=a. We assume that a > b. ???????

Change of Radix Consider a number 18. 18 in decimal system: 1810= 1(101) + 8(100) 18 in binary system: 1810= 1(24) + 0(23) + 0(22) + 1(21) + 0(20) 1810= 100102 18 in hexadecimal system 1810= 1(163) + 2(160) 1810= F216

Base conversion The Division Theorem can be used in base conversion. In order to convert a positive number x to base b: Apply the Theorem to x and b, getting x = q0b + r0 Apply the theorem to quotient q0and b, getting q0= q1b + r1. Apply the theorem to quotient q1and b, getting q1= q2b + r2. Continue until some quotient qn= 0. Then x in base b is rnrn-1 r1r0. Comment: This works for positive x. To convert a negative x, convert its absolute value and tack a minus sign. Negative base b needs to be handled differently.

Example: Write 6137 in octal system We are interested in finding r0, r1, . such that 6137 = r0+ r18 + r282+ .. + rk8k. = r0+ 8(r1+ r28 + .. + rk8k-1) = r0+ 8(r1+ 8(r2+ .+ rk8k-2)) Apply Division Theorem to 6136 and 8 getting 6137 = 767x8+1 (r0) Apply the theorem to quotient 767 and 8, getting 767 = 95x8+ 7( r1). Apply the theorem to quotient 95 and 8, getting 95 = 11 x 8 + 7(r2). Continue until some quotient qn= 0. 6137 = 1 + 7 x 8 + 7 x 82 + 3 x 83+ 1 x 84.

Binary system In the field of computer science, the binary number system is very important. In this system, the number are written in binary. 1910= 100112 For negative integers, in binary system, we use a popular method that enables us to perform addtion, subtraction, multiplication and (integer) division : two s complement method. Skipping this part. You should be familiar with two s complement and how it is used in arithmetic operations.

Primes Definition: A positive integer p greater than 1 is called prime if the only positive factors of p 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.

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 = 22 52 641 = 641 999 = 3 3 3 37 = 33 37 1024 = 2 2 2 2 2 2 2 2 2 2 = 210

Primes Any integer n > 1 that is not a prime is called composite. Lemma: Every composite number has a prime divisor: Proof by contradiction. Suppose there are positive composite numbers with no prime divisors. Let n be the smallest positive number with no prime factors. Well- ordering principle guarantees that n exists. Let m be a divisor of n (n is composite). Thus we have m is composite and m < n. This violates the condition that n is the smallest composite. Therefore, m must be prime and m divides n.

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.

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. a. Delete all the integers, other than 2, divisible by 2. b. Delete all the integers, other than 3, divisible by 3. c. Next, delete all the integers, other than 5, divisible by 5. d. Next, delete all the integers, other than 7, divisible by 7. e. Since all the remaining integers are not divisible by any of the previous integers, other than 1, the primes are: {2,3,7,11,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89, 97}

The Sieve of Erastosthenes 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.

How many primes? Theorem: There are infinitely many primes. (Please read the proof in the text.) Example: We know 2, 3, 5, 7, 11 are first few primes. We can show that 2.3.5.7.11+1=2311 is a prime.

Mersenne Primes Definition: Prime numbers of the form 2p 1 , wherep is prime, are called Mersenne primes. 22 1 = 3, 23 1 = 7, 25 1 = 31 , and 27 1 = 127 are Mersenne primes. 211 1 = 2047 is not a Mersenne primesince 2047 = 23 89. There is an efficient test for determining if 2p 1 is prime. The largest known prime numbers are Mersenne primes. As of mid 2011, 47 Mersenne primes were known, the largest is 243,112,609 1, which has nearly 13 million decimal digits. The Great Internet Mersenne Prime Search (GIMPS) is a distributed computing project to search for new Mersenne Primes.

Generating Primes The problem of generating large primes is of both theoretical and practical interest. 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.

Practice Problems No. 2, 4, 12, 15, 16 (page 230)

The Greatest Common Divisor (GCD) Suppose y and z are integers, and that x is a positive integer such that x | y and x | z. Then x is said to be a common divisor of y and z. Examples: The common divisors of 60 and 80 are 1,2,3,4,6,12. The common divisors of -4 and 18 are 1 and 2. We are interested in the greatest common divisor of integers y and z.

GCD Definition: Let a, b Z where a 0 or b 0. Then c Z+ is called a greatest common divisor of a,b if (a) c|a and c|b (b) for any common divisor d of a and b, we have d|c.

Uniqueness of GCD Theorem: For all a, b Z+, there exists a unique c Z+ that is the greatest common divisor of a, b. Proof: Let S = {as + bt| s, t Z, as + st > 0}. S is non-empty. Let c be the smallest integer number in S (by the well ordering principle). Any divisor d of a and b also divides c. If c does not divide a, there exist q and r > 0 such that a= qc +r. In this case r= a qc = a q(as + bt) = a(1 qs) + b( - qt). Therefore, r (< c) also belongs to S. This is not possible since c is the smallest element of S. Therefore, c |a and c|b. Finally, if c and d are greatest common divisors, then c|d and d|c. Thus, c=d. The GCD of a and b is unique.

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(b,c) when a>b and c is the remainder when a is divided by b. Example: Find gcd(287,91): 287 = 91 3 + 14 91 = 14 6 + 7 14 = 7 2 + 0 Divide 287 by 91 Divide 91 by 14 Divide 14 by 7 Stopping condition gcd(287, 91) = gcd(91, 14) = gcd(14, 7) = 7

Euclidean Algorithm The Euclidean algorithm expressed in pseudocode is: proceduregcd(a, b: positive integers) x := a y := b while y 0 r := xmody x := y y := r returnx {gcd(a,b) is x}

Example Find d = gcd(821,123) and integers u and v such that d = 821u +123v. Solved in the class.

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 greatest common divisor and the least common multiple of two integers are related by: Theorem: Let a and b be positive integers. Then ab = gcd(a,b) lcm(a,b)

More on primes Definition: The integers a and b are relatively prime if their greatest common divisor is 1. Example: 17 and 22 Definition: The integers a1, a2, , an are pairwiserelatively prime if gcd(ai, aj)= 1 whenever 1 i<j n. Example: Determine whether the integers 10, 17 and 21 are pairwise relatively prime. Solution: Because gcd(10,17) = 1, gcd(10,21) = 1, and gcd(17,21) = 1, 10, 17, and 21 are pairwise relatively prime. Example: Determine whether the integers 10, 19, and 24 are pairwise relatively prime. Solution: Because gcd(10,24) = 2, 10, 19, and 24 are not pairwise relatively prime.