5.1 Number Theory 217 Profile in Mathematics Srinivasa Ramanujan One of the most interesting mathematicians of modern times is Srinivasa Ramanujan (1887– 1920). Born in India, he virtually taught himself higher mathematics. He went to England to study with the number theorist G. H. Hardy. Hardy tells the story of a taxicab ride he took to visit Ramanujan. The cab was numbered 1729, and he challenged the young Indian to determine anything interesting in that number. Without hesitating, Ramanujan pointed out that it was the smallest positive integer that could be represented in two different ways as the sum of two cubes: 1 12 3 3 + and 9 10. 3 3 + The 2015 movie The Man Who Knew Infinity depicts Ramanujan’s life and career along with his friendship with Hardy. Example 3 Prime Factorization by Division Write 1500 as a product of prime numbers. Solution Because 1500 is an even number, the smallest prime number that divides it is 2. Divide 1500 by 2. Place the quotient, 750, below the 1500. Continue to divide each quotient by the smallest prime number that divides it. 2 1500 2 750 3 375 5 125 5 25 5 The final quotient, 5, is a prime number, so we stop. The prime factorization is determined by multiplying all divisors on the left side and the final prime number quotient as shown by the shaded arrow. Thus, the prime factorization of 1500 is 223555 2 35. 2 3 ⋅ ⋅ ⋅ ⋅ ⋅ = ⋅ ⋅ 7 Now try Exercise 37 Note that despite the different methods used in Examples 2 and 3, the answer is the same. Greatest Common Divisor The discussion in Section 5.3 of how to reduce fractions makes use of the greatest common divisor (GCD). We will now discuss how to determine the GCD of a set of numbers. One technique of determining the GCD is to use prime factorization. Definition: Greatest Common Divisor The greatest common divisor (GCD) of a set of natural numbers is the largest natural number that divides (without remainder) every number in that set. What is the GCD of 12 and 18? One way to determine the GCD is to list the divisors (or factors) of 12 and 18: 1 2 3 6 1 2 3 6 Divisors of 12 , , ,4, ,12 Divisors of 18 , , , ,9,18 { } { } The common divisors are 1, 2, 3, and 6, in bold above. Therefore, the greatest common divisor is 6. If the numbers are large, this method of determining the GCD is not practical. The GCD can be determined more efficiently by using prime factorization. TO DETERMINE THE GREATEST COMMON DIVISOR OF TWO OR MORE NUMBERS 1. Determine the prime factorization of each number. 2. List each prime factor with the smallest exponent that appears in each of the prime factorizations. 3. Determine the product of the factors determined in Step 2. PROCEDURE
RkJQdWJsaXNoZXIy NjM5ODQ=