Lecture 2 - Radford
Lecture 17 Integers, Divisions and Algorithms
Goals and Objectives:
• Understand integer divisibility and its algorithm complexity
• Understand Euclidean and extended Euclidean algorithms
Read 2.4, 2.5, p. 153-179
1. Definition. a|b (or a divides b, or a is a factor of b or b is a multiple of a) if a, b are integers, a[pic]0, and there exists an integer c such that b=a*c
Example. How many positive integers that are [pic] n and are divisible by an integer d?
Answer: 0 to at most [pic]
Example:
How many positive integers that is no more than 25 and is a multiple of 4?
Answer: positive multiple of 4 are 4, 8, 12, 16, 20, 24
The number =[pic] = 6
Definition. A positive integer is a prime if the only positive factor of itself is 1 and itself.
A positive integer is a composite if it is greater than 1 and it is not a prime.
Definition. The fundamental theorem of arithmetic (Prime Factorization)
Every positive integer greater than 1 can be written uniquely as a prime or as the product of 2 or more primes where the prime factors are written in order of non-decreasing size.
Example. Find prime factorization of 414.
Answer; 414=2*32 *23
Theorem. If n is a composite integer, then n has a prime divisor less than or equal to [pic]
Example. Prove that 331 is a prime.
Proof: use proof by contradiction. If 331 is a composite, then there is a prime divisor [pic] [pic] < 19
Try all primes under 19: 2, 3, 5, 7, 11, 13, 17. They are not factors of 331. Contradiction.
Definition. A Mersenne prime has the form 2p -1, where p is a prime.
Example. 3=22 -1, 7=23 -1 and 31=25 -1 are Mersenne primes. However 211 -1=2047 is not since 2047=23*89
Example. The largest Mersenne prime found (by GIMPS) so far (2006) can be found at
Definition. The greatest common divisor (gcd(a, b)) of integers a and b, a, b are not both 0. gcd(a,b)= the largest integer c such that c|a and c|b
Example gcd (2, 0)=2, gcd(8, 12)=4
Definition integers a and b are relatively prime if gcd(a, b)=1
Example. Integers 4 and 9 are relatively prime since gcd(4, 9)=1 even though both 4 and 9 are composites.
Theorem. If the prime factorizations of a and b are
a = p1a1* … * pnan
b = p1b1* … * pnbn
Then gcd (a, b) = p1 min(a1, b1) * … * pn min(an, bn)
Ex. gcd(414,662)=2 since
414=2*32*23
662=2*331
Theorem. The time complexity to use prime factorization to find gcd(a,b) is O([pic]), where n=max(a, b)
A more efficient algorithm to find gcd is called Euclidean algorithm, dated in 265 B.C. that uses the following property:
Theorem. Let a, b, q, r are positive integers, b [pic] a and a=b*q+r, where 0 [pic] r < b. Then gcd(b, a) = gcd (a, b) = gcd (b, r)
Note: if either a or b are negative integer, then you can take out the negative sign so if a ................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- marketing management pdf lecture notes
- strategic management lecture notes pdf
- strategic management lecture notes
- philosophy 101 lecture notes
- philosophy lecture notes
- philosophy of education lecture notes
- financial management lecture notes
- financial management lecture notes pdf
- business management lecture notes
- introduction to philosophy lecture notes
- business management lecture notes pdf
- introduction to management lecture notes