Mathematics
Lowest Common Multiple
The lowest common multiple (LCM) of two or more numbers is the smallest multiple that is exactly divisible by each of the numbers. It is used to find a common denominator when adding or subtracting fractions, and to solve various mathematical problems involving multiples. The LCM is an important concept in number theory and arithmetic.
Written by Perlego with AI-assistance
Related key terms
1 of 5
12 Key excerpts on "Lowest Common Multiple"
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Learning Press(Publisher)
________________________ WORLD TECHNOLOGIES ________________________ Chapter 2 Least Common Multiple and Euclidean Algorithm Least common multiple In arithmetic and number theory, the least common multiple (also called the Lowest Common Multiple or smallest common multiple ) of two integers a and b , usually denoted by LCM( a , b ) , is the smallest positive integer that is a multiple of both a and b . It is familiar from grade-school arithmetic as the lowest common denominator that must be determined before two fractions can be added. This definition may be extended to rational numbers a and b : the LCM is the smallest positive rational number that is an integer multiple of both a and b . (In fact, the definition may be extended to any two real numbers whose ratio is a rational number.) If either a or b is 0, LCM( a , b ) is defined to be zero. The LCM of more than two integers or rational numbers is well-defined: it is the smallest number that is an integer multiple of each of them. Examples Integer What is the LCM of 4 and 6? Multiples of 4 are: 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, ... and the multiples of 6 are: 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, ... Common multiples of 4 and 6 are simply the numbers that are in both lists: ________________________ WORLD TECHNOLOGIES ________________________ 12, 24, 36, 48, 60, .... So the least common multiple of 4 and 6 is the smallest one of those: 12 = 3 × 4 = 2 × 6. Rational What is the LCM of and The multiples of are: and the multiples of are: Therefore, their LCM is the smallest number on both lists. What is the LCM of and The multiples of are: and the multiples of are: So their LCM is Note that, by definition, if a and b are two rationals (or integers), there are integers m and n such that LCM( a , b ) = m × a = n × b .
eBook - PDFMathematical Practices, Mathematics for Teachers
Activities, Models, and Real-Life Examples
- Ron Larson, Robyn Silbey(Authors)
- 2014(Publication Date)
- Cengage Learning EMEA(Publisher)
Euclidean geometry is also named after Euclid. Classroom Tip Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 184 Chapter 5 Number Theory The Least Common Multiple Definition of Least Common Multiple (LCM) The least common multiple (LCM) of two or more natural numbers is the least natural number that is a multiple of both or all of the natural numbers. The notation for the least common multiple of a and b is written as LCM(a, b). To find the LCM(a, b), write the prime factorizations of a and b using two intersecting sets. The least common multiple is the product of the factors in all three regions. a = 20 b = 12 2 2 5 3 Common factors Example a = 20, b = 12 a = 2 ⋅ 2 ⋅ 5, b = 2 ⋅ 2 ⋅ 3 LCM(20, 12) = 2 ⋅ 2 ⋅ 3 ⋅ 5 = 60 If the only common factor of a and b is 1, then the LCM(a, b) = a ⋅ b. Example LCM(3, 5) = 3 ⋅ 5 = 15 EXAMPLE 5 Finding the Least Common Multiple Find the least common multiple of each pair of whole numbers. a. 6, 10 b. 18, 20 SOLUTION a. Begin by writing the prime factorization of each number. a = 6: 6 b = 10: 10 2 3 2 5 So, 6 = 2 ⋅ 3 and 10 = 2 ⋅ 5. Next, use a diagram to organize the prime factors of a and b. The least common multiple of 6 and 10 is 2 ⋅ 3 ⋅ 5 = 30. b. Begin by writing the prime factorization of each number. a = 18: 18 b = 20: 20 2 9 4 5 3 3 2 2 So, 18 = 2 ⋅ 3 ⋅ 3 and 20 = 2 ⋅ 2 ⋅ 5. Next, use a diagram to organize the prime factors of a and b. The least common multiple of 18 and 20 is 2 ⋅ 2 ⋅ 3 ⋅ 3 ⋅ 5 = 180. The least common multiple of 1 and any nonzero whole number is simply the whole number.
- Alan Tussy, Diane Koenig(Authors)
- 2018(Publication Date)
- Cengage Learning EMEA(Publisher)
Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. CHAPTER 1 • Whole Numbers 86 If we extend each list, it soon becomes apparent that 3 and 4 have infinitely many common multiples. The common multiples of 3 and 4 are: 12, 24, 36, 48, 60, 72, … Because 12 is the smallest number that is a multiple of both 3 and 4, it is called the least common multiple (LCM) of 3 and 4. We can write this in compact form as: LCM (3, 4) 12 Read as “The least common multiple of 3 and 4 is 12.” The Least Common Multiple (LCM) The least common multiple of two whole numbers is the smallest common multiple of the numbers. We have seen that the LCM of 3 and 4 is 12. It is important to note that 12 is divisible by both 3 and 4. 12 3 4 and 12 4 3 This observation illustrates an important relationship between divisibility and the least common multiple. The Least Common Multiple (LCM) The least common multiple of two whole numbers is the smallest whole number that is divisible by both of those numbers. When finding the LCM of two numbers, writing both lists of multiples can be tiresome. From the previous definition of LCM, it follows that we need only list the multiples of the larger number. The LCM is simply the first multiple of the larger number that is divisible by the smaller number. For example, to find the LCM of 3 and 4 , we observe that The multiples of 4 are: 4, 8, 12, 16, 20, 24, … 4 is not 8 is not 12 is divisible by 3. divisible by 3. divisible by 3. Recall that one number is divisible by another if, when dividing them, we get a remainder of 0. Since 12 is the first multiple of 4 that is divisible by 3, the LCM of 3 and 4 is 12. As expected, this is the same result that we obtained using the two-list method.
eBook - PDF- Robert Reys, Mary Lindquist, Diana V. Lambdin, Nancy L. Smith, Anna Rogers, Audrey Cooke, Bronwyn Ewing, Kylie Robson(Authors)
- 2021(Publication Date)
- Wiley(Publisher)
Extending from the second lesson idea is the well-known craft/art of string designs and mathematics (www.stringartfun.co.uk/string-art-math), which uses multiples in a circle or other geometric design. Greatest common factor and Lowest Common Multiple Once factors and multiples of individual numbers have been met; the next logical step is to look at pairs of numbers. This is important for later mathematics. The most common questions asked are: ‘What is the largest number that is a factor of both numbers (greatest common factor)?’ ‘What is the smallest number that is a multiple of both the numbers (Lowest Common Multiple)?’ Understanding these concepts depends mainly on knowing how to find factors and multiples and maintaining clear thinking about which is which. Procedures for finding the greatest common factor (GCF) and least common multiple (LCM) are very similar. While there is an advantage in knowing these methods, relying on a rote approach can confuse children who do not yet understand factors and multiples and have no real purpose for finding the greatest or least quantity. The LCM is most often used when finding a common denominator of fractions for addition and subtraction, which is not required until Year 7. Prior to that, denominators which are the same or related are used for addition and subtraction in Years 5 and 6. The GCF is used to simplify fractions, which begins during Year 6 when children compare fractions with related denominators and make connections between equivalent fractions. In secondary school, children will be using these skills for algebraic equations. With the prevalence of digital technology, neither of these skills are as important as they once were due to alternative methods that are more effective and accurate when applied to decimals rather than fractions. The simplest procedure for GCF or LCM is to list the factors or multiples of the two numbers and identify the greatest or least number that is common to both lists.
eBook - PDF- J. F. Humphreys, M. Y. Prest(Authors)
- 2004(Publication Date)
- Cambridge University Press(Publisher)
More generally, given non-zero integers a 1 , . . . , a n , we define their least common multiple , lcm( a 1 , . . . , a n ), to be the (unique) positive integer m which satisfies a i | m for all i and, whenever an integer c satisfies a i | c for all i , we have m | c . For instance lcm(6, 15, 4) = lcm(lcm(6, 15), 4) = lcm(30, 4) = 60. We shall see in Section 1.3 how to interpret both the greatest common divisor and the least common multiple of integers a and b in terms of the decomposition of a and b as products of primes. All of the concepts and most of the results of this section are to be found in the Elements of Euclid (who flourished around 300 bc ). Euclid’s origins are unknown but he was one of the scholars called to the Museum of Alexandria. The Museum was a centre of scholarship and research established by Ptolemy, a general of Alexander the Great, who, after the latter’s death in 323 bc , gained control of the Egyptian part of the empire. 1.2 Mathematical induction 15 The Elements probably was a textbook covering all the elementary mathe-matics of the time. It was not the first such ‘elements’ but its success was such that it drove its predecessors into oblivion. It is not known how much of the mathematics of the Elements originated with Euclid: perhaps he added no new results; but the organisation, the attention to rigour and, no doubt, some of the proofs, were his. It is generally thought that the algebra in Euclid originated considerably earlier. No original manuscript of the Elements survives, and modern editions have been reconstructed from various recensions (revised editions) and commen-taries by other authors. Exercises 1.1 1. For each of the following pairs a , b of integers, find the greatest common divisor d of a and b and express d in the form ar + bs : (i) a = 7 and b = 11; (ii) a = − 28 and b = − 63; (iii) a = 91 and b = 126; (iv) a = 630 and b = 132; (v) a = 7245 and b = 4784; (vi) a = 6499 and b = 4288.
eBook - PDF- Charles P. McKeague(Author)
- 2015(Publication Date)
- XYZ Textbooks(Publisher)
Don’t dwell on questions and evaluations of the class that can be used as excuses for not doing well. If you want to succeed in this course, focus your energy and efforts toward success, rather than distracting yourself from your goals. Be Resilient Don’t let a temporary disappointment keep you from succeeding in this course, or any class in college. Failing a test or quiz, or having a difficult time on some topics, is normal. No one goes through college without some setbacks. A low grade on a test or quiz is simply a signal that you need to reevaluate your study habits. Intend to Succeed I have a few students who simply go through the motions of studying without intending to master the material. You need to study with the intention of being successful in the course. Intend to master the material, no matter what it takes. © CEFutcher/iStockPhoto 3.1 3.1 Least Common Multiple 147 Least Common Multiple In the next section we will begin our work with adding fractions. When the fractions we are adding have different denominators, we must first change to equivalent fractions that have the same denominator. To practice finding the new denominator, we introduce the Least Common Multiple for a set of numbers. In other words, all the numbers involved must divide into the least common multiple exactly. That is, they divide it without leaving a remainder. Find the least common multiple (LCM) for each set of numbers. a. 3 and 6 b. 2 and 6 c. 48 and 12 Solution We approach these problems intuitively by asking the questions below. a. What is the smallest number divisible by 3 and 6? The answer is 6. b. What is the smallest number divisible by 2 and 6? The answer is 6. c. What is the smallest number divisible by 48 and 12? The answer is 48. Find the LCM for each set of numbers. a. 2, 5, and 10 b. 8, 12, and 24 Solution a. The smallest number that divides 2, 5, and 10 is 10: 2 divides it five times, 5 divides it two times, and 10 divides it once.
eBook - PDF- Lynn Marecek, MaryAnne Anthony-Smith, Andrea Honeycutt Mathis(Authors)
- 2020(Publication Date)
- Openstax(Publisher)
List the first several multiples of each number. Look for multiples common to both lists. If there are no common multiples in the lists, write out additional multiples for each number. Look for the smallest number that is common to both lists. This number is the LCM. Step 1. Step 2. Step 3. Step 4. Chapter 2 The Language of Algebra 169 The smallest number to appear on both lists is 60, so 60 is the least common multiple of 15 and 20. Notice that 120 is on both lists, too. It is a common multiple, but it is not the least common multiple. TRY IT : : 2.103 Find the least common multiple (LCM) of the given numbers: 9 and 12 TRY IT : : 2.104 Find the least common multiple (LCM) of the given numbers: 18 and 24 Prime Factors Method Another way to find the least common multiple of two numbers is to use their prime factors. We’ll use this method to find the LCM of 12 and 18. We start by finding the prime factorization of each number. 12 = 2 ⋅ 2 ⋅ 3 18 = 2 ⋅ 3 ⋅ 3 Then we write each number as a product of primes, matching primes vertically when possible. 12 = 2 ⋅ 2 ⋅ 3 18 = 2 ⋅ 3 ⋅ 3 Now we bring down the primes in each column. The LCM is the product of these factors. Notice that the prime factors of 12 and the prime factors of 18 are included in the LCM. By matching up the common primes, each common prime factor is used only once. This ensures that 36 is the least common multiple. EXAMPLE 2.53 Find the LCM of 15 and 18 using the prime factors method. Solution Write each number as a product of primes. Write each number as a product of primes, matching primes vertically when possible. Bring down the primes in each column. Multiply the factors to get the LCM. LCM = 2 ⋅ 3 ⋅ 3 ⋅ 5 The LCM of 15 and 18 is 90. HOW TO : : FIND THE LCM USING THE PRIME FACTORS METHOD. Find the prime factorization of each number. Write each number as a product of primes, matching primes vertically when possible. Bring down the primes in each column. Multiply the factors to get the LCM.
eBook - PDFNeverending Fractions
An Introduction to Continued Fractions
- Jonathan Borwein, Alf van der Poorten, Jeffrey Shallit, Wadim Zudilin(Authors)
- 2014(Publication Date)
- Cambridge University Press(Publisher)
We get the least common multiple by specialization t = ±1: lcm(a, b) = |ab|/ gcd(a, b). Thus, formula (1.5) can be written in the required form M = lcm(a, b)t with t ∈ Z. The previous lemma gives a simple and efficient algorithm for computing the least common multiple for a set a 1 , a 2 , . . . , a n of arbitrary length n ≥ 2. Namely, we have the formula lcm(a 1 , a 2 , a 3 , a 4 , . . . , a n ) = lcm(lcm(. . . lcm(lcm(lcm(a 1 , a 2 ), a 3 ), a 4 ), . . . ), a n ), while the least common multiple of just two numbers is computed by lcm(a, b) = |ab| gcd(a, b) . Exercise 1.12 Show that, for a pair of relatively prime integers a and b, the linear equation ax − by = 1 has infinitely many solutions in integers x, y. Hint This can be split into two parts: First, show (using either an inductive argument or the Euclidean algorithm) that there exists at least one solution of the equation, say x 0 , y 0 , and, second, that the pair x = x 0 + bt, y = y 0 + at is a solution for any t ∈ Z. 1.2 Primes 5 1.2 Primes An integer exceeding 1 always has at least two distinct divisors, namely, 1 and itself. If these two divisors exhaust the list of all positive divisors of such an integer then the integer is called a prime number; otherwise, the integer (> 1) is called a composite number. Lemma 1.13 The least positive divisor, different from 1, of an integer a > 1 is a prime. Proof The set A = {2, 3, . . . , a} is not empty and finite and contains at least one divisor (namely, a) of the given integer a; thus we can choose the smallest such divisor, say b. If b is not prime then it has a divisor c such that 1 < c < b, so that c ∈ A. But then Lemma 1.1 implies that c divides a, which contradicts our choice of b. The next lemma, while simple, is very potent. Lemma 1.14 The least positive divisor, different from 1, of a composite inte- ger a > 1 does not exceed √ a. Proof Let b > 1 be the least positive divisor of a. Write a = bc; since a is composite we have b < a, so that c > 1.
eBook - ePubFrom Frege to Gödel
A Source Book in Mathematical Logic, 1879–1931
- Jean van Heijenoort(Author)
- 2002(Publication Date)
- Harvard University Press(Publisher)
c .36b. (a /c ) − (b /c ) = (a − b )/c .§ 6. GREATEST COMMON DIVISOR AND LEAST COMMON MULTIPLE
The customary definitions of the greatest common divisor and the least common multiple of two numbers make use of apparent variables that range over an infinite domain. In Schröder’s symbols these definitions in fact have the following form:(c is the greatest common divisor of a and b )(c is the least common multiple of a and b )Since, however, x a follows (Corollary 1 to Theorem 25) from D(a , x ), the infinite domain over which the variable ranges in the definition of the greatest common divisor can at once be cut down to a finite one, and we can just as well write(c is the greatest common divisor of a and b )A disadvantage of this definition is, however, that it is asymmetric with respect to a and b . But this, too, can easily be remedied, since over the sign Π we can write a + b instead of the upper bound a , or even better Min(a , b ), where Min(a , b ) is the minimum of the numbers a and b . For the definition of the least common multiple such a reduction of the range of the variable to a finite domain cannot be carried out quite so easily.In what follows I shall introduce these notions in a different way, one that avoids apparent variables altogether. In doing this, however, I must make use of the recursive method of definition in a different way from before (though, as I shall soon show, the difference is purely superficial). Until now we have always given recursive definitions strictly as follows: we defined a notion for the number 1 and then, on the assumption that the definition for an arbitrarily given number n is already complete, we defined the notion for n + 1. Furthermore, a formal logical principle will be used here, namely, that we can give separate definitions for each one of mutually exclusive cases. I introduce two descriptive functions of two variables a and b , namely a ∧ b and a ∨ b
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Learning Press(Publisher)
• It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a complete distributive lattice with gcd as meet and lcm as join operation. This extension of the definition is also compatible with the generalization for commutative rings given below. ________________________ WORLD TECHNOLOGIES ________________________ • In a Cartesian coordinate system, gcd( a , b ) can be interpreted as the number of points with integral coordinates on the straight line joining the points (0, 0) and ( a , b ), excluding (0, 0). Probabilities and expected value In 1972, J. E. Nymann showed that the probability that k independently chosen integers are coprime is 1/ ζ ( k ). This result was extended in 1987 to show that the probability that k random integers has greatest common divisor d is d -k /ζ ( k ). Using this information, the expected value of the greatest common divisor function can be seen (informally) to not exist when k = 2. In this case the probability that the gcd equals d is d −2 /ζ(2), and since ζ(2) = π 2 /6 we have This last summation is the harmonic series, which diverges. However, when k ≥ 3, the expected value is well-defined, and by the above argument, it is For k = 3, this is approximately equal to 1.3684. For k = 4, it is approximately 1.1106. The gcd in commutative rings The greatest common divisor can more generally be defined for elements of an arbitrary commutative ring. If R is a commutative ring, and a and b are in R , then an element d of R is called a common divisor of a and b if it divides both a and b (that is, if there are elements x and y in R such that d · x = a and d · y = b ). If d is a common divisor of a and b , and every common divisor of a and b divides d , then d is called a greatest common divisor of a and b . Note that with this definition, two elements a and b may very well have several greatest common divisors, or none at all.
eBook - PDFDiscrete Mathematics
Proof Techniques and Mathematical Structures
- R C Penner(Author)
- 1999(Publication Date)
- WSPC(Publisher)
,a n } is a non-empty subset of IN, and this set therefore has a least element by Theorem 3.7.3. This least element is called the least common multiple (to be abbreviated simply 1cm) of A and is denoted [ai,..., a n ]. For an example, we conclude that [4,3] = 12 by simply observing that no natural number less than 12 is a common multiple of 4 and 3. For another example, consider d = [3,4,18], and observe that [3,4,18] = [3,2 2 ,2 • 3 2 ], so some power of 2 divides d and some power of 3 divides d. To find out which powers, notice that 2 2 and 3 2 must divide d, and in fact, d = 2 2 -3 2 = 36 is a common multiple of {3,4,18}. Enumerating the natural numbers less than 36, we conclude that 36 is actually the Zcra, so 36 = [3,4,18]. EXERCISES 4.1 COMMON MULTIPLES 1. Compute the least common multiple of each of the following sets. (a) {2,4,8} (b) {2,6,8} (c) {5,7,12} (d) {2,3,4,5,12} 2. Prove that if ca and c|6, then c(ma -f nb) for any integers a,b,c,m,n. 3. Prove that the least common multiple of a non-empty set A C IN is uniquely determined. 4. Show that if a, b G IN satsify ab and 6|a, then a = b. 5. Prove or disprove each of the following for a, 6, c, d G IN. (a) If 6|ac, then bc. (b) If ab and c|d, then acbd. (c) If a|6, then abc. (d) If a(b + c), then ab or ac. 6. Prove or disprove each of the following for a, 6, c, d G IN. (a) If ac and 6|c, then abc. (b) If [a,6] = d = [6, c], then [a,c] = d. (c) ab if and only if ac|6c. (d) 2|[a(o + 1)] and 3|[a(a + l)(a + 2)] 7. Prove each of the following by induction on n G IN. (a) 7|(2 3n - 1) (b) 8|(3 2n + 7) (c) 3|[2 n + (-l) n + 1 ] 154 Chapter 4 Elementary Number Theory 8. Suppose that a, b G IN and prove each of the following. (a) ab{a + 6)! [HINT: Argue by induction on a + 6.] (b) Use part (a) to show that (a + l)(a + 2) • • • (a + fc) is divisible by fc! for each a, fc G IN .
eBook - PDF- John Peterson, Robert Smith(Authors)
- 2018(Publication Date)
- Cengage Learning EMEA(Publisher)
Procedure for Determining Lowest Common Denominators When it is difficult to determine the lowest common denominator, a procedure using prime factors is used. A factor is a number being multiplied. A prime number is a whole number other than 0 and 1 that is divisible only by itself and 1. Some examples of prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, and 23. A prime factor is a factor that is a prime number. To determine the lowest common denominator, first factor each of the denomina-tors into prime factors. List each prime factor as many times as it appears in any one denominator. Multiply all of the prime factors listed. EXAMPLES 1. Find the lowest common denominator of 5 6 , 1 5 , and 3 16 . Factor each of the denominators into prime factors. The prime factors 3 and 5 are each used as factors only once. List these factors. The prime factor 2 is used once for denominator 6 and four times for denominator 16. List 2 as a factor four times. 6 5 2 3 3 5 5 5 s prime d 16 5 2 3 2 3 2 3 2 3 3 5 3 2 3 2 3 2 3 2 5 240 Ans Copyright 2019 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 60 Section I FUNDAMENTALS OF GENERAL MATHEMATICS If the same prime factor is used in 2 or more denominators, it is listed only for the denominator for which it is used the greatest number of times. Multiply all prime factors listed to obtain the lowest common denominator. 2. Find the lowest common denominator of 9 10 , 3 8 , 4 9 , and 7 15 . Factor each of the denominators into prime factors. Multiply all prime factors listed to obtain the lowest common denominator.
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
