Factor a and b using g: a = gx, b = gy where x and y are relatively prime. Slide 35 L935 lcm in terms of gcd Proof THM: lcm(a,b) = ab / gcd(a,b) Proof. lcm(9,21) = 63 THM: lcm(a,b) = ab / gcd(a,b) Slide 34 L934 lcm in terms of gcd Proof THM: lcm(a,b) = ab / gcd(a,b) Proof. lcm(9,21) Slide 33 L933 Least Common Multiple A: 1. Equivalently: lcm(a,b) is biggest number which divides any x divisible by both a and b Q: Find the lcm s: 1. Slide 32 L932 Least Common Multiple DEF: The least common multiple of a, and b (lcm(a,b) ) is the smallest number m which is divisible by both a and b. In general: The number of d-multiples less than N is given by: | is another answer. However, since 1,000,000 isn t divisible by 15, need to round down to the highest multiple of 15 less than 1,000,000 so answer is 1,000,000/15. Since 1 out of 15 numbers is a multiple of 15, if 1,000,000 were were divisible by 15, answer would be exactly 1,000,000/15. Q: How many positive multiples of 15 are less than 1,000,000? Slide 11 L911 Formula for Number of Multiples up to Given n A: Listing is too much of a hassle. 24 | 0: true, 0 is divisible by every number (0 = 24 0) Slide 9 L99 Formula for Number of Multiples up to given n Q: How many positive multiples of 15 are less than 100? Slide 10 L910 Formula for Number of Multiples up to given n A: Just list them: 15, 30, 45, 60, 75, 80, 95. 0 | 24: false, only 0 is divisible by 0 5. 77 | 7: false bigger number can t divide smaller positive number 2. Examples Q: Which of the following is true? 1. NOTE: Students find notation confusing, and think of | in the reverse fashion, perhaps confuse pipe with forward slash / Slide 7 L97 Divisors. The pipe symbol | denotes divides so the situation is summarized by: b | a c | a. Then b and c are said to divide (or are factors) of a, while a is said to be a multiple of b (as well as of c). Slide 6 L96 Divisors DEF: Let a, b and c be integers such that a = b c. We need to develop various machinery (notations and techniques) for manipulating numbers before can describe algorithms in a natural fashion. Slide 5 L95 Importance of Number Theory The encryption algorithms depend heavily on modular arithmetic. E.G., of great importance in COMS 4180 Network Security. Of utmost importance to everyone from Bill Gates, to the CIA, to Osama Bin Laden. Number theory is crucial for encryption algorithms. Slide 3 L93 Agenda Section 2.3 Divisors Primality Fundamental Theorem of Arithmetic Division Algorithm Greatest common divisors/least common multiples Relative Primality Modular arithmetic Caesar s Cipher Slide 4 L94 Importance of Number Theory Before the dawn of computers, many viewed number theory as last bastion of pure math which could not be useful and must be enjoyed only for its aesthetic beauty. Basic Number Theory Zeph Grunschlag Slide 2 L92 Announcement Last 4 problems will be added tonight to HW4.
0 kommentar(er)
