How to find the least common multiple. Why introduce the concepts of "Greatest Common Divisor (GCD)" and "Least Common Multiple (LCM)" of numbers in a school mathematics course
To learn how to find the greatest common divisor of two or more numbers, you need to understand what natural, prime and complex numbers are.
A natural number is any number that is used to count integers.
If a natural number can only be divided by itself and one, then it is called prime.
All natural numbers can be divided by themselves and one, but the only even prime number is 2, all others can be divided by two. Therefore, only odd numbers can be prime.
There are a lot of prime numbers, there is no complete list of them. To find the GCD, it is convenient to use special tables with such numbers.
Most natural numbers can be divided not only by one, themselves, but also by other numbers. So, for example, the number 15 can be divided by 3 and 5. All of them are called divisors of the number 15.
Thus, the divisor of any A is the number by which it can be divided without a remainder. If a number has more than two natural divisors, it is called composite.
The number 30 has such divisors as 1, 3, 5, 6, 15, 30.
You can see that 15 and 30 have the same divisors 1, 3, 5, 15. The greatest common divisor of these two numbers is 15.
Thus, the common divisor of the numbers A and B is the number by which you can divide them completely. The maximum can be considered the maximum total number by which they can be divided.
To solve problems, the following abbreviated inscription is used:
GCD (A; B).
For example, GCD (15; 30) = 30.
To write down all divisors of a natural number, the notation is used:
D(15) = (1, 3, 5, 15)
gcd (9; 15) = 1
In this example, natural numbers have only one common divisor. They are called coprime, respectively, the unit is their greatest common divisor.
How to find the greatest common divisor of numbers
To find the GCD of several numbers, you need:
Find all divisors of each natural number separately, that is, decompose them into factors (prime numbers);
Select all the same factors for given numbers;
Multiply them together.
For example, to calculate the greatest common divisor of 30 and 56, you would write the following:
In order not to get confused with , it is convenient to write the multipliers using vertical columns. On the left side of the line, you need to place the dividend, and on the right - the divisor. Under the dividend, you should indicate the resulting quotient.
So, in the right column will be all the factors needed for the solution.
Identical divisors (factors found) can be underlined for convenience. They should be rewritten and multiplied and the greatest common divisor should be written down.
GCD (30; 56) = 2 * 5 = 10
It's really that simple to find the greatest common divisor of numbers. With a little practice, you can do it almost automatically.
The material presented below is a logical continuation of the theory from the article under the heading LCM - least common multiple, definition, examples, relationship between LCM and GCD. Here we will talk about finding the least common multiple (LCM), and pay special attention to solving examples. Let us first show how the LCM of two numbers is calculated in terms of the GCD of these numbers. Next, consider finding the least common multiple by factoring numbers into prime factors. After that, we will focus on finding the LCM of three or more numbers, and also pay attention to the calculation of the LCM of negative numbers.
Page navigation.
Calculation of the least common multiple (LCM) through gcd
One way to find the least common multiple is based on the relationship between LCM and GCD. The existing relationship between LCM and GCD allows you to calculate the least common multiple of two positive integers through the known greatest common divisor. The corresponding formula has the form LCM(a, b)=a b: GCM(a, b) . Consider examples of finding the LCM according to the above formula.
Example.
Find the least common multiple of the two numbers 126 and 70 .
Solution.
In this example a=126 , b=70 . Let us use the relationship between LCM and GCD expressed by the formula LCM(a, b)=a b: GCM(a, b). That is, first we have to find the greatest common divisor of the numbers 70 and 126, after which we can calculate the LCM of these numbers according to the written formula.
Find gcd(126, 70) using Euclid's algorithm: 126=70 1+56 , 70=56 1+14 , 56=14 4 , hence gcd(126, 70)=14 .
Now we find the required least common multiple: LCM(126, 70)=126 70: GCM(126, 70)= 126 70:14=630 .
Answer:
LCM(126, 70)=630 .
Example.
What is LCM(68, 34) ?
Solution.
Because 68 is evenly divisible by 34 , then gcd(68, 34)=34 . Now we calculate the least common multiple: LCM(68, 34)=68 34: LCM(68, 34)= 68 34:34=68 .
Answer:
LCM(68, 34)=68 .
Note that the previous example fits the following rule for finding the LCM for positive integers a and b : if the number a is divisible by b , then the least common multiple of these numbers is a .
Finding the LCM by Factoring Numbers into Prime Factors
Another way to find the least common multiple is based on factoring numbers into prime factors. If we make a product of all prime factors of these numbers, after which we exclude from this product all common prime factors that are present in the expansions of these numbers, then the resulting product will be equal to the least common multiple of these numbers.
The announced rule for finding the LCM follows from the equality LCM(a, b)=a b: GCM(a, b). Indeed, the product of the numbers a and b is equal to the product of all the factors involved in the expansions of the numbers a and b. In turn, gcd(a, b) is equal to the product of all prime factors that are simultaneously present in the expansions of the numbers a and b (which is described in the section on finding the gcd using the decomposition of numbers into prime factors).
Let's take an example. Let we know that 75=3 5 5 and 210=2 3 5 7 . Compose the product of all factors of these expansions: 2 3 3 5 5 5 7 . Now we exclude from this product all the factors that are present both in the expansion of the number 75 and in the expansion of the number 210 (such factors are 3 and 5), then the product will take the form 2 3 5 5 7 . The value of this product is equal to the least common multiple of the numbers 75 and 210, that is, LCM(75, 210)= 2 3 5 5 7=1 050.
Example.
After factoring the numbers 441 and 700 into prime factors, find the least common multiple of these numbers.
Solution.
Let's decompose the numbers 441 and 700 into prime factors:
We get 441=3 3 7 7 and 700=2 2 5 5 7 .
Now let's make a product of all the factors involved in the expansions of these numbers: 2 2 3 3 5 5 7 7 7 . Let us exclude from this product all the factors that are simultaneously present in both expansions (there is only one such factor - this is the number 7): 2 2 3 3 5 5 7 7 . In this way, LCM(441, 700)=2 2 3 3 5 5 7 7=44 100.
Answer:
LCM(441, 700)= 44 100 .
The rule for finding the LCM using the decomposition of numbers into prime factors can be formulated a little differently. If we add the missing factors from the expansion of the number b to the factors from the expansion of the number a, then the value of the resulting product will be equal to the least common multiple of the numbers a and b.
For example, let's take all the same numbers 75 and 210, their expansions into prime factors are as follows: 75=3 5 5 and 210=2 3 5 7 . To the factors 3, 5 and 5 from the decomposition of the number 75, we add the missing factors 2 and 7 from the decomposition of the number 210, we get the product 2 3 5 5 7 , the value of which is LCM(75, 210) .
Example.
Find the least common multiple of 84 and 648.
Solution.
We first obtain the decomposition of the numbers 84 and 648 into prime factors. They look like 84=2 2 3 7 and 648=2 2 2 3 3 3 3 . To the factors 2 , 2 , 3 and 7 from the decomposition of the number 84 we add the missing factors 2 , 3 , 3 and 3 from the decomposition of the number 648 , we get the product 2 2 2 3 3 3 3 7 , which is equal to 4 536 . Thus, the desired least common multiple of the numbers 84 and 648 is 4,536.
Answer:
LCM(84, 648)=4 536 .
Finding the LCM of three or more numbers
The least common multiple of three or more numbers can be found by successively finding the LCM of two numbers. Recall the corresponding theorem, which gives a way to find the LCM of three or more numbers.
Theorem.
Let positive integers a 1 , a 2 , …, a k be given, the least common multiple m k of these numbers is found in the sequential calculation m 2 = LCM (a 1 , a 2) , m 3 = LCM (m 2 , a 3) , … , m k =LCM(m k−1 , a k) .
Consider the application of this theorem on the example of finding the least common multiple of four numbers.
Example.
Find the LCM of the four numbers 140 , 9 , 54 and 250 .
Solution.
In this example a 1 =140 , a 2 =9 , a 3 =54 , a 4 =250 .
First we find m 2 \u003d LCM (a 1, a 2) \u003d LCM (140, 9). To do this, using the Euclidean algorithm, we determine gcd(140, 9) , we have 140=9 15+5 , 9=5 1+4 , 5=4 1+1 , 4=1 4 , therefore, gcd(140, 9)=1 , whence LCM(140, 9)=140 9: LCM(140, 9)= 140 9:1=1 260 . That is, m 2 =1 260 .
Now we find m 3 \u003d LCM (m 2, a 3) \u003d LCM (1 260, 54). Let's calculate it through gcd(1 260, 54) , which is also determined by the Euclid algorithm: 1 260=54 23+18 , 54=18 3 . Then gcd(1 260, 54)=18 , whence LCM(1 260, 54)= 1 260 54:gcd(1 260, 54)= 1 260 54:18=3 780 . That is, m 3 \u003d 3 780.
Left to find m 4 \u003d LCM (m 3, a 4) \u003d LCM (3 780, 250). To do this, we find GCD(3 780, 250) using the Euclid algorithm: 3 780=250 15+30 , 250=30 8+10 , 30=10 3 . Therefore, gcd(3 780, 250)=10 , whence gcd(3 780, 250)= 3 780 250:gcd(3 780, 250)= 3 780 250:10=94 500 . That is, m 4 \u003d 94 500.
So the least common multiple of the original four numbers is 94,500.
Answer:
LCM(140, 9, 54, 250)=94,500.
In many cases, the least common multiple of three or more numbers is conveniently found using prime factorizations of given numbers. In this case, the following rule should be followed. The least common multiple of several numbers is equal to the product, which is composed as follows: the missing factors from the expansion of the second number are added to all the factors from the expansion of the first number, the missing factors from the expansion of the third number are added to the obtained factors, and so on.
Consider an example of finding the least common multiple using the decomposition of numbers into prime factors.
Example.
Find the least common multiple of five numbers 84 , 6 , 48 , 7 , 143 .
Solution.
First, we obtain the expansions of these numbers into prime factors: 84=2 2 3 7 , 6=2 3 , 48=2 2 2 2 3 , 7 prime factors) and 143=11 13 .
To find the LCM of these numbers, to the factors of the first number 84 (they are 2 , 2 , 3 and 7 ) you need to add the missing factors from the expansion of the second number 6 . The expansion of the number 6 does not contain missing factors, since both 2 and 3 are already present in the expansion of the first number 84 . Further to the factors 2 , 2 , 3 and 7 we add the missing factors 2 and 2 from the expansion of the third number 48 , we get a set of factors 2 , 2 , 2 , 2 , 3 and 7 . There is no need to add factors to this set in the next step, since 7 is already contained in it. Finally, to the factors 2 , 2 , 2 , 2 , 3 and 7 we add the missing factors 11 and 13 from the expansion of the number 143 . We get the product 2 2 2 2 3 7 11 13 , which is equal to 48 048 .
Consider the solution of the following problem. The boy's step is 75 cm, and the girl's step is 60 cm. It is necessary to find the smallest distance at which both of them will take an integer number of steps.
Solution. The entire path that the guys will go through must be divisible by 60 and 70 without a remainder, since they must each take an integer number of steps. In other words, the answer must be a multiple of both 75 and 60.
First, we will write out all multiples, for the number 75. We get:
- 75, 150, 225, 300, 375, 450, 525, 600, 675, … .
Now let's write out the numbers that will be a multiple of 60. We get:
- 60, 120, 180, 240, 300, 360, 420, 480, 540, 600, 660, … .
Now we find the numbers that are in both rows.
- Common multiples of numbers will be numbers, 300, 600, etc.
The smallest of them is the number 300. In this case, it will be called the least common multiple of the numbers 75 and 60.
Returning to the condition of the problem, the smallest distance at which the guys take an integer number of steps will be 300 cm. The boy will go this way in 4 steps, and the girl will need to take 5 steps.
Finding the Least Common Multiple
- The least common multiple of two natural numbers a and b is the smallest natural number that is a multiple of both a and b.
In order to find the least common multiple of two numbers, it is not necessary to write down all the multiples for these numbers in a row.
You can use the following method.
How to find the least common multiple
First, you need to decompose these numbers into prime factors.
- 60 = 2*2*3*5,
- 75=3*5*5.
Now let's write down all the factors that are in the expansion of the first number (2,2,3,5) and add to it all the missing factors from the expansion of the second number (5).
As a result, we get a series of prime numbers: 2,2,3,5,5. The product of these numbers will be the least common factor for these numbers. 2*2*3*5*5 = 300.
General scheme for finding the least common multiple
- 1. Decompose numbers into prime factors.
- 2. Write down the prime factors that are part of one of them.
- 3. Add to these factors all those that are in the decomposition of the rest, but not in the selected one.
- 4. Find the product of all the factors written out.
This method is universal. It can be used to find the least common multiple of any number of natural numbers.
Greatest Common Divisor
Definition 2
If a natural number a is divisible by a natural number $b$, then $b$ is called a divisor of $a$, and the number $a$ is called a multiple of $b$.
Let $a$ and $b$ be natural numbers. The number $c$ is called a common divisor for both $a$ and $b$.
The set of common divisors of the numbers $a$ and $b$ is finite, since none of these divisors can be greater than $a$. This means that among these divisors there is the largest one, which is called the greatest common divisor of the numbers $a$ and $b$, and the notation is used to denote it:
$gcd \ (a;b) \ or \ D \ (a;b)$
To find the greatest common divisor of two numbers:
- Find the product of the numbers found in step 2. The resulting number will be the desired greatest common divisor.
Example 1
Find the gcd of the numbers $121$ and $132.$
$242=2\cdot 11\cdot 11$
$132=2\cdot 2\cdot 3\cdot 11$
Choose the numbers that are included in the expansion of these numbers
$242=2\cdot 11\cdot 11$
$132=2\cdot 2\cdot 3\cdot 11$
Find the product of the numbers found in step 2. The resulting number will be the desired greatest common divisor.
$gcd=2\cdot 11=22$
Example 2
Find the GCD of monomials $63$ and $81$.
We will find according to the presented algorithm. For this:
Let's decompose numbers into prime factors
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
We select the numbers that are included in the expansion of these numbers
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
Let's find the product of the numbers found in step 2. The resulting number will be the desired greatest common divisor.
$gcd=3\cdot 3=9$
You can find the GCD of two numbers in another way, using the set of divisors of numbers.
Example 3
Find the gcd of the numbers $48$ and $60$.
Solution:
Find the set of divisors of $48$: $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\right\)$
Now let's find the set of divisors of $60$:$\ \left\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right\)$
Let's find the intersection of these sets: $\left\((\rm 1,2,3,4,6,12)\right\)$ - this set will determine the set of common divisors of the numbers $48$ and $60$. The largest element in this set will be the number $12$. So the greatest common divisor of $48$ and $60$ is $12$.
Definition of NOC
Definition 3
common multiple of natural numbers$a$ and $b$ is a natural number that is a multiple of both $a$ and $b$.
Common multiples of numbers are numbers that are divisible by the original without a remainder. For example, for the numbers $25$ and $50$, the common multiples will be the numbers $50,100,150,200$, etc.
The least common multiple will be called the least common multiple and denoted by LCM$(a;b)$ or K$(a;b).$
To find the LCM of two numbers, you need:
- Decompose numbers into prime factors
- Write out the factors that are part of the first number and add to them the factors that are part of the second and do not go to the first
Example 4
Find the LCM of the numbers $99$ and $77$.
We will find according to the presented algorithm. For this
Decompose numbers into prime factors
$99=3\cdot 3\cdot 11$
Write down the factors included in the first
add to them factors that are part of the second and do not go to the first
Find the product of the numbers found in step 2. The resulting number will be the desired least common multiple
$LCC=3\cdot 3\cdot 11\cdot 7=693$
Compiling lists of divisors of numbers is often very time consuming. There is a way to find GCD called Euclid's algorithm.
Statements on which Euclid's algorithm is based:
If $a$ and $b$ are natural numbers, and $a\vdots b$, then $D(a;b)=b$
If $a$ and $b$ are natural numbers such that $b
Using $D(a;b)= D(a-b;b)$, we can successively decrease the numbers under consideration until we reach a pair of numbers such that one of them is divisible by the other. Then the smaller of these numbers will be the desired greatest common divisor for the numbers $a$ and $b$.
Properties of GCD and LCM
- Any common multiple of $a$ and $b$ is divisible by K$(a;b)$
- If $a\vdots b$ , then K$(a;b)=a$
If K$(a;b)=k$ and $m$-natural number, then K$(am;bm)=km$
If $d$ is a common divisor for $a$ and $b$, then K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d) $
If $a\vdots c$ and $b\vdots c$ , then $\frac(ab)(c)$ is a common multiple of $a$ and $b$
For any natural numbers $a$ and $b$ the equality
$D(a;b)\cdot K(a;b)=ab$
Any common divisor of $a$ and $b$ is a divisor of $D(a;b)$
Lancinova Aisa
Download:
Preview:
To use the preview of presentations, create a Google account (account) and sign in: https://accounts.google.com
Slides captions:
Tasks for GCD and LCM of numbers The work of a 6th grade student of the MKOU "Kamyshovskaya OOSh" Lantsinova Aisa Supervisor Goryaeva Zoya Erdnigoryaevna, teacher of mathematics p. Kamyshovo, 2013
An example of finding the GCD of the numbers 50, 75 and 325. 1) Let's decompose the numbers 50, 75 and 325 into prime factors. 50= 2 ∙ 5 ∙ 5 75= 3 ∙ 5 ∙ 5 325= 5 ∙ 5 ∙ 13 50= 2 ∙ 5 ∙ 5 75= 3 ∙ 5 ∙ 5 325= 5 ∙ 5 ∙13 divide without a remainder the numbers a and b are called the greatest common divisor of these numbers.
An example of finding the LCM of the numbers 72, 99 and 117. 1) Let us factorize the numbers 72, 99 and 117. Write out the factors included in the expansion of one of the numbers 2 ∙ 2 ∙ 2 ∙ 3 ∙ 3 and add to them the missing factors of the remaining numbers. 2 ∙ 2 ∙ 2 ∙ 3 ∙ 3 ∙ 11 ∙ 13 3) Find the product of the resulting factors. 2 ∙ 2 ∙ 2 ∙ 3 ∙ 3 ∙ 11 ∙ 13= 10296 Answer: LCM (72, 99 and 117) = 10296 The least common multiple of natural numbers a and b is the smallest natural number that is a multiple of a and b.
A sheet of cardboard has the shape of a rectangle, the length of which is 48 cm and the width is 40 cm. This sheet must be cut without waste into equal squares. What are the largest squares that can be obtained from this sheet and how many? Solution: 1) S = a ∙ b is the area of the rectangle. S \u003d 48 ∙ 40 \u003d 1960 cm². is the area of the cardboard. 2) a - the side of the square 48: a - the number of squares that can be laid along the length of the cardboard. 40: a - the number of squares that can be laid across the width of the cardboard. 3) GCD (40 and 48) \u003d 8 (cm) - the side of the square. 4) S \u003d a² - the area of \u200b\u200bone square. S \u003d 8² \u003d 64 (cm².) - the area of \u200b\u200bone square. 5) 1960: 64 = 30 (number of squares). Answer: 30 squares with a side of 8 cm each. Tasks for GCD
The fireplace in the room must be laid out with finishing tiles in the shape of a square. How many tiles are needed for a 195 ͯ 156 cm fireplace and what are the largest tile sizes? Solution: 1) S = 196 ͯ 156 = 30420 (cm ²) - S of the fireplace surface. 2) GCD (195 and 156) = 39 (cm) - side of the tile. 3) S = a² = 39² = 1521 (cm²) - area of 1 tile. 4) 30420: = 20 (pieces). Answer: 20 tiles measuring 39 ͯ 39 (cm). Tasks for GCD
A garden plot measuring 54 ͯ 48 m around the perimeter must be fenced off, for this, concrete pillars must be placed at regular intervals. How many poles must be brought for the site, and at what maximum distance from each other will the poles stand? Solution: 1) P = 2(a + b) – site perimeter. P \u003d 2 (54 + 48) \u003d 204 m. 2) GCD (54 and 48) \u003d 6 (m) - the distance between the pillars. 3) 204: 6 = 34 (pillars). Answer: 34 pillars, at a distance of 6 m. Tasks for GCD
Out of 210 burgundy, 126 white, 294 red roses, bouquets were collected, and in each bouquet the number of roses of the same color is equal. What is the largest number of bouquets made from these roses and how many roses of each color are in one bouquet? Solution: 1) GCD (210, 126 and 294) = 42 (bouquets). 2) 210: 42 = 5 (burgundy roses). 3) 126: 42 = 3 (white roses). 4) 294: 42 = 7 (red roses). Answer: 42 bouquets: 5 burgundy, 3 white, 7 red roses in each bouquet. Tasks for GCD
Tanya and Masha bought the same number of mailboxes. Tanya paid 90 rubles, and Masha paid 5 rubles. more. How much does one set cost? How many sets did each buy? Solution: 1) Masha paid 90 + 5 = 95 (rubles). 2) GCD (90 and 95) = 5 (rubles) - the price of 1 set. 3) 980: 5 = 18 (sets) - bought by Tanya. 4) 95: 5 = 19 (sets) - Masha bought. Answer: 5 rubles, 18 sets, 19 sets. Tasks for GCD
Three tourist boat trips start in the port city, the first of which lasts 15 days, the second - 20 and the third - 12 days. Returning to the port, the ships on the same day again go on a voyage. Motor ships left the port on all three routes today. In how many days will they sail together for the first time? How many trips will each ship make? Solution: 1) NOC (15.20 and 12) = 60 (days) - meeting time. 2) 60: 15 = 4 (voyages) - 1 ship. 3) 60: 20 = 3 (voyages) - 2 motor ship. 4) 60: 12 = 5 (voyages) - 3 motor ship. Answer: 60 days, 4 flights, 3 flights, 5 flights. Tasks for the NOC
Masha bought eggs for the Bear in the store. On the way to the forest, she realized that the number of eggs is divisible by 2,3,5,10 and 15. How many eggs did Masha buy? Solution: LCM (2;3;5;10;15) = 30 (eggs) Answer: Masha bought 30 eggs. Tasks for the NOC
It is required to make a box with a square bottom for stacking boxes measuring 16 ͯ 20 cm. What should be the shortest side of the square bottom to fit the boxes tightly into the box? Solution: 1) NOC (16 and 20) = 80 (boxes). 2) S = a ∙ b is the area of 1 box. S \u003d 16 ∙ 20 \u003d 320 (cm ²) - the area of the bottom of 1 box. 3) 320 ∙ 80 = 25600 (cm ²) - square bottom area. 4) S \u003d a² \u003d a ∙ a 25600 \u003d 160 ∙ 160 - the dimensions of the box. Answer: 160 cm is the side of the square bottom. Tasks for the NOC
Along the road from point K there are power poles every 45 m. It was decided to replace these poles with others, placing them at a distance of 60 m from each other. How many poles were there and how many will they stand? Solution: 1) NOK (45 and 60) = 180. 2) 180: 45 = 4 - there were pillars. 3) 180: 60 = 3 - there were pillars. Answer: 4 pillars, 3 pillars. Tasks for the NOC
How many soldiers are marching on the parade ground if they march in formation of 12 people in a line and change into a column of 18 people in a line? Solution: 1) NOC (12 and 18) = 36 (people) - marching. Answer: 36 people. Tasks for the NOC