Greatest Common Divisor Given positive integers m and n, a common divisor is an integer d such that d | m and d | n. The largest such integer d is called the greatest common divisor, the gcd, of m and n. In this section we will look at methods of finding the gcd of two given numbers. We look at the gcd problem in two ways: Suppose that we know m = 2372134173 and that n = 245275172. A common divisor must be made up of prime powers that are common to both m and n. The possible primes here are 2, 7 and 17 (we exclude the primes 5 and 13 since they only appear in one of the numbers). Since we are looking for the greatest common divisor we must take the smallest power of each of these primes that is common to both m and n -- 23 divides both but 24 does not! Thus we construct the gcd of these numbers as d = 2372172. In this manner, once we know the prime factorization of the numbers m and n it is easy to read off their gcd. The method is not restricted to just two numbers of course. Suppose that we want the gcd of 60, 210 and 450. Rewrite these numbers as 223151, 21315171 and 213252. The gcd is then d = 213151 = 30. Suppose that we are given m and n but not their prime factorization. Sometimes it is difficult to factor numbers and this makes the above method impractical. In this case we can use what is known as the Euclidean Algorithm. The idea is simple if we understand that when something is true of one side of an equation then it is true of the other side also. Let us illustrate by trying to find d, the gcd of 12 378 and 3054. Write 12378 = 4 3054 + 162 and note that if d | 12 378 and d | 3054 then it must be that d | 162 ( if d divides the left hand side of the equation then it must divide the right hand side, but we already are assuming that it divides 3054 so that d | 162). How does this help? What it tells us is that the gcd of 12 378 and 3054 is the same as the gcd of 3054 and 162, i.e. we have reduced the problem to one dealing with smaller numbers. We thus can repeat the process and write 3054 = 18 162 + 138 and conclude that we want the gcd of 162 and 138. Repeating we write 162 = 1 138 + 24 138 = 5 24 + 18 24 = 1 18 + 6 18 = 3 6 + 0. The last non-zero remainder, 6 in this case, is the required gcd. (This is so since it is clear that 6 is the gcd of 6 and 18 and thus is the gcd of 18 and 24 and thus is ... the gcd of 3054 and 12 378.) Another example: find the gcd of 252 and 198. 252 = 1 198 + 54 198 = 3 54 + 36 54 = 1 36 + 18 36 = 2 18 + 0 gcd of 252 and 198 is 18. Least Common Multiple Suppose that we know m = 2372134173 and that n = 245275172. A common multiple must be made up of all the prime powers that appear in either m or n. The possible primes here are 2, 5, 7, 13 and 17. Since we are looking for the least common multiple we must take the largest power of each of these primes that appears in either m or n -- 24 divides n but does not divide m so we must take 24. Thus we construct the lcm of these numbers as q = 245275134173. In this manner, once we know the prime factorization of the numbers m and n it is easy to read off their lcm. The method is not restricted to just two numbers of course. Suppose that we want the lcm of 60, 210 and 450. Rewrite these numbers as 223151, 21315171 and 213252. The lcm is then q = 2232527 = 6300. A particular relationship between m, n, their gcd and lcm reveals another way in which to find the lcm of two numbers. Let us look at the numbers which we worked with above, m = 2372134173 and that n = 245275172. Their gcd is d = 2372172 and their lcm is q = 245275134173. Look at m n and compare it to the product of their gcd and lcm: m n = 2372134173 245275172 = 2324527275134173172 = 275277134175 d q = 2372172 245275134173 = 2324527275134172173 = 275277134175 The same thing! That is m n = d q. We will not go into depth as to why this always works, but the important idea is that in the gcd we pick prime powers common to both while in the lcm we pick prime powers that appear in either. Thus, let's find the lcm of 252 and 198. We saw earlier that the gcd is 18, thus 252 198 = 18 lcm and thus the lcm is q = (252 x 198) / 18 = 2772. Of course you should note that if, for example, we know m, n and their lcm we could just as easily use this method to find the gcd, i.e. 252 198 = gcd 2772 and thus the gcd is d = (252 198) / 2772 = 18.