CMPSC 40 Lecture 17: Lecture 17 Primes, Induction, and Recursion
Document Summary
Finding the gcd using prime factorizations where each exponent is a nonegative integer, and where all primes occurring in either prime. The least common multiple can also be computed from the prime factorizations: The greatest common divisor and the least common multiple of two integers are related: 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. Definition: the integers and are relatively prime if their greatest common divisor is. Definition: the integers are pairwise relatively prime if whenever. Suppose the prime factorizations of and are: , factorization are included in both. Definition: the least common multiple of the positive integers and is the smallest positive integer that is divisible by both and. Proof by contradiction: suppose that the positive integer can be written as a product of primes in two distinct ways: and.
