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.

Google Online Preview   Download