Greatest common divisor of two integers. What is a node. Division. dividend: divisor = quotient
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
Find the greatest common factor gcd (36 ; 24)
Solution steps
Method number 1
36
- composite number
24
- composite number
Let's expand the number 36
36:
2
= 18
18:
2
= 9
- is divisible by a prime number 2
9:
3
=
3
is divisible by the prime number 3.
Let's expand the number 24 into prime factors and highlight them in green. We begin to select a divisor from prime numbers, starting with the smallest prime number 2, until the quotient is a prime number
24:
2
= 12
- is divisible by a prime number 2
12:
2
= 6
- is divisible by a prime number 2
6:
2
=
3
We complete the division, since 3 is a prime number
2) Highlight in blue and write out the common factors
36
=
2
⋅
2
⋅
3
⋅
3
24
=
2
⋅
2
⋅
2
⋅
3
Common multipliers (36 ; 24): 2, 2, 3
3) Now, to find the GCD, you need to multiply the common factors
Answer: GCD (36; 24) = 2 ∙ 2 ∙ 3 = 12
Method number 2
1) Find all possible divisors of numbers (36; 24). To do this, we alternately divide the number 36 into divisors from 1 to 36, the number 24 into divisors from 1 to 24. If the number is divisible without a remainder, then we write the divisor in the list of divisors.
For number 36
36:
1
= 36;
36:
2
= 18;
36:
3
= 12;
36:
4
= 9;
36:
6
= 6;
36:
9
= 4;
36:
12
= 3;
36:
18
= 2;
36:
36
= 1;
For number 24 write down all the cases when it is divisible without a remainder:
24:
1
= 24;
24:
2
= 12;
24:
3
= 8;
24:
4
= 6;
24:
6
= 4;
24:
8
= 3;
24:
12
= 2;
24:
24
= 1;
2) Let's write out all the common divisors of the numbers (36; 24) and highlight the largest one in green, this will be the greatest common divisor of the GCD of numbers (36; 24)
Common divisors of numbers (36; 24): 1, 2, 3, 4, 6, 12
Answer: GCD (36; 24) = 12
Find the least common multiple of the LCM (52 ; 49)
Solution steps
Method number 1
1) Let's decompose the numbers into prime factors. To do this, check whether each of the numbers is prime (if the number is prime, then it cannot be decomposed into prime factors, and it is itself its decomposition)
52
- composite number
49
- composite number
Let's expand the number 52 into prime factors and highlight them in green. We begin to select a divisor from prime numbers, starting with the smallest prime number 2, until the quotient is a prime number
52:
2
= 26
- is divisible by a prime number 2
26:
2
=
13
is divisible by the prime number 2.
We complete the division, since 13 is a prime number
Let's expand the number 49 into prime factors and highlight them in green. We begin to select a divisor from prime numbers, starting with the smallest prime number 2, until the quotient is a prime number
49:
7
=
7
is divisible by the prime number 7.
We complete the division, since 7 is a prime number
2) First of all, write down the factors of the largest number, and then the smaller number. Let's find the missing factors, highlight in blue in the expansion of the smaller number the factors that were not included in the expansion of the larger number.
52
= 2 ∙ 2 ∙ 13
49
=
7
∙
7
3) Now, to find the LCM, you need to multiply the factors of a larger number with the missing factors, which are highlighted in blue
LCM (52 ; 49) = 2 ∙ 2 ∙ 13 ∙ 7 ∙ 7 = 2548
Method number 2
1) Find all possible multiples of numbers (52; 49). To do this, alternately multiply the number 52 by the numbers from 1 to 49, the number 49 by the numbers from 1 to 52.
Select all multiples 52 in green:
52 ∙ 1 =
52
;
52 ∙ 2 =
104
;
52 ∙ 3 =
156
;
52 ∙ 4 =
208
;
52 ∙ 5 =
260
;
52 ∙ 6 =
312
;
52 ∙ 7 =
364
;
52 ∙ 8 =
416
;
52 ∙ 9 =
468
;
52 ∙ 10 =
520
;
52 ∙ 11 =
572
;
52 ∙ 12 =
624
;
52 ∙ 13 =
676
;
52 ∙ 14 =
728
;
52 ∙ 15 =
780
;
52 ∙ 16 =
832
;
52 ∙ 17 =
884
;
52 ∙ 18 =
936
;
52 ∙ 19 =
988
;
52 ∙ 20 =
1040
;
52 ∙ 21 =
1092
;
52 ∙ 22 =
1144
;
52 ∙ 23 =
1196
;
52 ∙ 24 =
1248
;
52 ∙ 25 =
1300
;
52 ∙ 26 =
1352
;
52 ∙ 27 =
1404
;
52 ∙ 28 =
1456
;
52 ∙ 29 =
1508
;
52 ∙ 30 =
1560
;
52 ∙ 31 =
1612
;
52 ∙ 32 =
1664
;
52 ∙ 33 =
1716
;
52 ∙ 34 =
1768
;
52 ∙ 35 =
1820
;
52 ∙ 36 =
1872
;
52 ∙ 37 =
1924
;
52 ∙ 38 =
1976
;
52 ∙ 39 =
2028
;
52 ∙ 40 =
2080
;
52 ∙ 41 =
2132
;
52 ∙ 42 =
2184
;
52 ∙ 43 =
2236
;
52 ∙ 44 =
2288
;
52 ∙ 45 =
2340
;
52 ∙ 46 =
2392
;
52 ∙ 47 =
2444
;
52 ∙ 48 =
2496
;
52 ∙ 49 =
2548
;
Select all multiples 49 in green:
49 ∙ 1 =
49
;
49 ∙ 2 =
98
;
49 ∙ 3 =
147
;
49 ∙ 4 =
196
;
49 ∙ 5 =
245
;
49 ∙ 6 =
294
;
49 ∙ 7 =
343
;
49 ∙ 8 =
392
;
49 ∙ 9 =
441
;
49 ∙ 10 =
490
;
49 ∙ 11 =
539
;
49 ∙ 12 =
588
;
49 ∙ 13 =
637
;
49 ∙ 14 =
686
;
49 ∙ 15 =
735
;
49 ∙ 16 =
784
;
49 ∙ 17 =
833
;
49 ∙ 18 =
882
;
49 ∙ 19 =
931
;
49 ∙ 20 =
980
;
49 ∙ 21 =
1029
;
49 ∙ 22 =
1078
;
49 ∙ 23 =
1127
;
49 ∙ 24 =
1176
;
49 ∙ 25 =
1225
;
49 ∙ 26 =
1274
;
49 ∙ 27 =
1323
;
49 ∙ 28 =
1372
;
49 ∙ 29 =
1421
;
49 ∙ 30 =
1470
;
49 ∙ 31 =
1519
;
49 ∙ 32 =
1568
;
49 ∙ 33 =
1617
;
49 ∙ 34 =
1666
;
49 ∙ 35 =
1715
;
49 ∙ 36 =
1764
;
49 ∙ 37 =
1813
;
49 ∙ 38 =
1862
;
49 ∙ 39 =
1911
;
49 ∙ 40 =
1960
;
49 ∙ 41 =
2009
;
49 ∙ 42 =
2058
;
49 ∙ 43 =
2107
;
49 ∙ 44 =
2156
;
49 ∙ 45 =
2205
;
49 ∙ 46 =
2254
;
49 ∙ 47 =
2303
;
49 ∙ 48 =
2352
;
49 ∙ 49 =
2401
;
49 ∙ 50 =
2450
;
49 ∙ 51 =
2499
;
49 ∙ 52 =
2548
;
2) Let's write down all the common multiples of the numbers (52; 49) and highlight the smallest one in green, this will be the least common multiple of the numbers (52; 49).
Common multiples of numbers (52; 49): 2548
Answer: LCM (52; 49) = 2548
But many natural numbers are evenly divisible by other natural numbers.
For example:
The number 12 is divisible by 1, by 2, by 3, by 4, by 6, by 12;
The number 36 is divisible by 1, by 2, by 3, by 4, by 6, by 12, by 18, by 36.
The numbers by which the number is divisible (for 12 it is 1, 2, 3, 4, 6 and 12) are called number divisors. Divisor of a natural number a is the natural number that divides the given number a without a trace. A natural number that has more than two factors is called composite .
Note that the numbers 12 and 36 have common divisors. These are the numbers: 1, 2, 3, 4, 6, 12. The largest divisor of these numbers is 12. The common divisor of these two numbers a And b is the number by which both given numbers are divisible without a remainder a And b.
common multiple several numbers is called the number that is divisible by each of these numbers. For example, the numbers 9, 18 and 45 have a common multiple of 180. But 90 and 360 are also their common multiples. Among all jcommon multiples, there is always the smallest, in this case it's 90. This number is called leastcommon multiple (LCM).
LCM is always a natural number, which must be greater than the largest of the numbers for which it is defined.
Least common multiple (LCM). Properties.
Commutativity:
Associativity:
In particular, if and are coprime numbers , then:
Least common multiple of two integers m And n is a divisor of all other common multiples m And n. Moreover, the set of common multiples m,n coincides with the set of multiples for LCM( m,n).
The asymptotics for can be expressed in terms of some number-theoretic functions.
So, Chebyshev function. As well as:
This follows from the definition and properties of the Landau function g(n).
What follows from the law of distribution of prime numbers.
Finding the least common multiple (LCM).
NOC( a, b) can be calculated in several ways:
1. If the greatest common divisor is known, you can use its relationship with the LCM:
2. Let the canonical decomposition of both numbers into prime factors be known:
where p 1 ,...,p k are various prime numbers, and d 1 ,...,dk And e 1 ,...,ek are non-negative integers (they can be zero if the corresponding prime is not in the decomposition).
Then LCM ( a,b) is calculated by the formula:
In other words, the LCM expansion contains all prime factors that are included in at least one of the number expansions a, b, and the largest of the two exponents of this factor is taken.
Example:
The calculation of the least common multiple of several numbers can be reduced to several successive calculations of the LCM of two numbers:
Rule. To find the LCM of a series of numbers, you need:
- decompose numbers into prime factors;
- transfer the largest expansion to the factors of the desired product (the product of the factors of the largest number of the given ones), and then add factors from the expansion of other numbers that do not occur in the first number or are in it a smaller number of times;
- the resulting product of prime factors will be the LCM of the given numbers.
Any two or more natural numbers have their own LCM. If the numbers are not multiples of each other or do not have the same factors in the expansion, then their LCM is equal to the product of these numbers.
The prime factors of the number 28 (2, 2, 7) were supplemented with a factor of 3 (the number 21), the resulting product (84) will be the smallest number that is divisible by 21 and 28.
The prime factors of the largest number 30 were supplemented with a factor of 5 of the number 25, the resulting product 150 is greater than the largest number 30 and is divisible by all given numbers without a remainder. This is the smallest possible product (150, 250, 300...) that all given numbers are multiples of.
The numbers 2,3,11,37 are prime, so their LCM is equal to the product of the given numbers.
rule. To calculate the LCM of prime numbers, you need to multiply all these numbers together.
Another option:
To find the least common multiple (LCM) of several numbers you need:
1) represent each number as a product of its prime factors, for example:
504 \u003d 2 2 2 3 3 7,
2) write down the powers of all prime factors:
504 \u003d 2 2 2 3 3 7 \u003d 2 3 3 2 7 1,
3) write down all prime divisors (multipliers) of each of these numbers;
4) choose the largest degree of each of them, found in all expansions of these numbers;
5) multiply these powers.
Example. Find the LCM of numbers: 168, 180 and 3024.
Solution. 168 \u003d 2 2 2 3 7 \u003d 2 3 3 1 7 1,
180 \u003d 2 2 3 3 5 \u003d 2 2 3 2 5 1,
3024 = 2 2 2 2 3 3 3 7 = 2 4 3 3 7 1 .
We write out the largest powers of all prime divisors and multiply them:
LCM = 2 4 3 3 5 1 7 1 = 15120.
The largest natural number by which the numbers a and b are divisible without remainder is called greatest common divisor these numbers. Denote GCD(a, b).
Consider finding the GCD using the example of two natural numbers 18 and 60:
18 = 2×3×3
60 = 2×2×3×5
18 = 2×3×3
60 = 2×2×3×5
324 , 111 And 432
Let's decompose the numbers into prime factors:
324 = 2×2×3×3×3×3
111 = 3×37
432 = 2×2×2×2×3×3×3
Delete from the first number, the factors of which are not in the second and third numbers, we get:
2 x 2 x 2 x 2 x 3 x 3 x 3 = 3
As a result of GCD( 324 , 111 , 432 )=3
Finding GCD with Euclid's Algorithm
The second way to find the greatest common divisor using Euclid's algorithm. Euclid's algorithm is the most efficient way to find GCD, using it you need to constantly find the remainder of the division of numbers and apply recurrent formula.
Recurrent formula for GCD, gcd(a, b)=gcd(b, a mod b), where a mod b is the remainder of dividing a by b.
Euclid's algorithm
Example Find the Greatest Common Divisor of Numbers 7920 And 594
Let's find GCD( 7920 , 594 ) using the Euclid algorithm, we will calculate the remainder of the division using a calculator.
- 7920 mod 594 = 7920 - 13 × 594 = 198
- 594 mod 198 = 594 - 3 × 198 = 0
As a result, we get GCD( 7920 , 594 ) = 198
Least common multiple
In order to find a common denominator when adding and subtracting fractions with different denominators, you need to know and be able to calculate least common multiple(NOC).
A multiple of the number "a" is a number that is itself divisible by the number "a" without a remainder.
Numbers that are multiples of 8 (that is, these numbers will be divided by 8 without a remainder): these are the numbers 16, 24, 32 ...
Multiples of 9: 18, 27, 36, 45…
There are infinitely many multiples of a given number a, in contrast to the divisors of the same number. Divisors - a finite number.
A common multiple of two natural numbers is a number that is evenly divisible by both of these numbers..
Least common multiple(LCM) of two or more natural numbers is the smallest natural number that is itself divisible by each of these numbers.
How to find the NOC
LCM can be found and written in two ways.
The first way to find the LCM
This method is usually used for small numbers.
- We write the multiples for each of the numbers in a line until there is a multiple that is the same for both numbers.
- A multiple of the number "a" is denoted by a capital letter "K".
Example. Find LCM 6 and 8.
The second way to find the LCM
This method is convenient to use to find the LCM for three or more numbers.
The number of identical factors in the expansions of numbers can be different.
LCM (24, 60) = 2 2 3 5 2
Answer: LCM (24, 60) = 120
You can also formalize finding the least common multiple (LCM) as follows. Let's find the LCM (12, 16, 24) .
24 = 2 2 2 3
As we can see from the expansion of numbers, all factors of 12 are included in the expansion of 24 (the largest of the numbers), so we add only one 2 from the expansion of the number 16 to the LCM.
LCM (12, 16, 24) = 2 2 2 3 2 = 48
Answer: LCM (12, 16, 24) = 48
Special cases of finding NOCs
For example, LCM(60, 15) = 60
Since coprime numbers have no common prime divisors, their least common multiple is equal to the product of these numbers.
On our site, you can also use a special calculator to find the least common multiple online to check your calculations.
If a natural number is only divisible by 1 and itself, then it is called prime.
Any natural number is always divisible by 1 and itself.
The number 2 is the smallest prime number. This is the only even prime number, the rest of the prime numbers are odd.
There are many prime numbers, and the first among them is the number 2. However, there is no last prime number. In the "For Study" section, you can download a table of prime numbers up to 997.
But many natural numbers are evenly divisible by other natural numbers.
- the number 12 is divisible by 1, by 2, by 3, by 4, by 6, by 12;
- 36 is divisible by 1, by 2, by 3, by 4, by 6, by 12, by 18, by 36.
- decompose the divisors of numbers into prime factors;
The numbers by which the number is evenly divisible (for 12 these are 1, 2, 3, 4, 6 and 12) are called the divisors of the number.
The divisor of a natural number a is such a natural number that divides the given number "a" without a remainder.
A natural number that has more than two factors is called a composite number.
Note that the numbers 12 and 36 have common divisors. These are numbers: 1, 2, 3, 4, 6, 12. The largest divisor of these numbers is 12.
The common divisor of two given numbers "a" and "b" is the number by which both given numbers "a" and "b" are divided without remainder.
Greatest Common Divisor(GCD) of two given numbers "a" and "b" is the largest number by which both numbers "a" and "b" are divisible without a remainder.
Briefly, the greatest common divisor of numbers "a" and "b" is written as follows:
Example: gcd (12; 36) = 12 .
The divisors of numbers in the solution record are denoted by a capital letter "D".
The numbers 7 and 9 have only one common divisor - the number 1. Such numbers are called coprime numbers.
Coprime numbers are natural numbers that have only one common divisor - the number 1. Their GCD is 1.
How to find the greatest common divisor
To find the gcd of two or more natural numbers you need:
Calculations are conveniently written using a vertical bar. To the left of the line, first write down the dividend, to the right - the divisor. Further in the left column we write down the values of private.
Let's explain right away with an example. Let's factorize the numbers 28 and 64 into prime factors.
- Underline the same prime factors in both numbers.
28 = 2 2 7
64 = 2 2 2 2 2 2
We find the product of identical prime factors and write down the answer;
GCD (28; 64) = 2 2 = 4
Answer: GCD (28; 64) = 4
You can arrange the location of the GCD in two ways: in a column (as was done above) or “in a line”.
The first way to write GCD
Find GCD 48 and 36.
GCD (48; 36) = 2 2 3 = 12
The second way to write GCD
Now let's write the GCD search solution in a line. Find GCD 10 and 15.
On our information site, you can also find the greatest common divisor online using the helper program to check your calculations.
Finding the least common multiple, methods, examples of finding the LCM.
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 integers positive numbers 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.
Find the least common multiple of the two numbers 126 and 70 .
In this example a=126 , b=70 . Let's use the link of LCM with GCD, which is 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:GCD(126, 70)= 126 70:14=630 .
What is LCM(68, 34) ?
Since 68 is evenly divisible by 34 , then gcd(68, 34)=34 . Now we calculate the least common multiple: LCM(68, 34)=68 34:GCD(68, 34)= 68 34: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 75 and 210 , that is, LCM(75, 210)= 2 3 5 5 7=1 050 .
After factoring the numbers 441 and 700 into prime factors, find the least common multiple of these numbers.
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 . So LCM(441, 700)=2 2 3 3 5 5 7 7=44 100 .
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 expansion of the number 75, we add the missing factors 2 and 7 from the expansion of the number 210, we get the product 2 3 5 5 7 , the value of which is LCM(75, 210) .
Find the least common multiple of 84 and 648.
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.
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.
Let positive integers a 1 , a 2 , …, ak be given, the least common multiple mk of these numbers is found in the sequential calculation m 2 = LCM (a 1 , a 2) , m 3 = LCM (m 2 , a 3) , … , mk =LCM(mk−1 , ak) .
Consider the application of this theorem on the example of finding the least common multiple of four numbers.
Find the LCM of the four numbers 140 , 9 , 54 and 250 .
First we find m 2 = LCM (a 1 , a 2) = 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: GCD(140, 9)= 140 9:1=1 260 . That is, m 2 =1 260 .
Now we find m 3 = LCM (m 2 , a 3) = 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.
It remains to find m 4 = LCM (m 3 , a 4) = 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 , hence LCM(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.
LCM(140, 9, 54, 250)=94500 .
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.
Find the least common multiple of five numbers 84 , 6 , 48 , 7 , 143 .
First, we obtain decompositions of these numbers into prime factors: 84=2 2 3 7 , 6=2 3 , 48=2 2 2 2 3 , 7 (7 is a prime number, it coincides with its decomposition into 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 .
Therefore, LCM(84, 6, 48, 7, 143)=48048 .
LCM(84, 6, 48, 7, 143)=48048 .
Finding the Least Common Multiple of Negative Numbers
Sometimes there are tasks in which you need to find the least common multiple of numbers, among which one, several or all numbers are negative. In these cases, all negative numbers must be replaced by their opposite numbers, after which the LCM of positive numbers should be found. This is the way to find the LCM of negative numbers. For example, LCM(54, −34)=LCM(54, 34) and LCM(−622, −46, −54, −888)= LCM(622, 46, 54, 888) .
We can do this because the set of multiples of a is the same as the set of multiples of −a (a and −a are opposite numbers). Indeed, let b be some multiple of a , then b is divisible by a , and the notion of divisibility asserts the existence of such an integer q that b=a q . But the equality b=(−a)·(−q) will also be true, which, by virtue of the same concept of divisibility, means that b is divisible by −a , that is, b is a multiple of −a . The converse statement is also true: if b is some multiple of −a , then b is also a multiple of a .
Find the least common multiple of the negative numbers −145 and −45.
Let's replace the negative numbers −145 and −45 with their opposite numbers 145 and 45 . We have LCM(−145, −45)=LCM(145, 45) . Having determined gcd(145, 45)=5 (for example, using the Euclid algorithm), we calculate LCM(145, 45)=145 45:gcd(145, 45)= 145 45:5=1 305 . Thus, the least common multiple of the negative integers −145 and −45 is 1,305 .
www.cleverstudents.ru
We continue to study division. In this lesson, we will look at concepts such as GCD And NOC.
GCD is the greatest common divisor.
NOC is the least common multiple.
The topic is rather boring, but it is necessary to understand it. Without understanding this topic, you will not be able to work effectively with fractions, which are a real obstacle in mathematics.
Greatest Common Divisor
Definition. Greatest Common Divisor of Numbers a And b a And b divided without remainder.
In order to understand this definition well, we substitute instead of variables a And b any two numbers, for example, instead of a variable a substitute the number 12, and instead of the variable b number 9. Now let's try to read this definition:
Greatest Common Divisor of Numbers 12 And 9 is the largest number by which 12 And 9 divided without remainder.
It is clear from the definition that we are talking about a common divisor of the numbers 12 and 9, and this divisor is the largest of all existing divisors. This greatest common divisor (gcd) must be found.
To find the greatest common divisor of two numbers, three methods are used. The first method is quite time-consuming, but it allows you to understand the essence of the topic well and feel its whole meaning.
The second and third methods are quite simple and make it possible to quickly find the GCD. We will consider all three methods. And what to apply in practice - you choose.
The first way is to find all possible divisors of two numbers and choose the largest of them. Let's consider this method in the following example: find the greatest common divisor of the numbers 12 and 9.
First, we find all possible divisors of the number 12. To do this, we divide 12 into all divisors in the range from 1 to 12. If the divisor allows us to divide 12 without a remainder, then we will highlight it in blue and make an appropriate explanation in brackets.
12: 1 = 12
(12 divided by 1 without a remainder, so 1 is a divisor of 12)
12: 2 = 6
(12 divided by 2 without a remainder, so 2 is a divisor of 12)
12: 3 = 4
(12 divided by 3 without a remainder, so 3 is a divisor of 12)
12: 4 = 3
(12 divided by 4 without a remainder, so 4 is a divisor of 12)
12:5 = 2 (2 left)
(12 is not divided by 5 without a remainder, so 5 is not a divisor of 12)
12: 6 = 2
(12 divided by 6 without a remainder, so 6 is a divisor of 12)
12: 7 = 1 (5 left)
(12 is not divided by 7 without a remainder, so 7 is not a divisor of 12)
12: 8 = 1 (4 left)
(12 is not divided by 8 without a remainder, so 8 is not a divisor of 12)
12:9 = 1 (3 left)
(12 is not divided by 9 without a remainder, so 9 is not a divisor of 12)
12: 10 = 1 (2 left)
(12 is not divided by 10 without a remainder, so 10 is not a divisor of 12)
12:11 = 1 (1 left)
(12 is not divided by 11 without a remainder, so 11 is not a divisor of 12)
12: 12 = 1
(12 divided by 12 without a remainder, so 12 is a divisor of 12)
Now let's find the divisors of the number 9. To do this, check all the divisors from 1 to 9
9: 1 = 9
(9 divided by 1 without a remainder, so 1 is a divisor of 9)
9: 2 = 4 (1 left)
(9 is not divided by 2 without a remainder, so 2 is not a divisor of 9)
9: 3 = 3
(9 divided by 3 without a remainder, so 3 is a divisor of 9)
9: 4 = 2 (1 left)
(9 is not divided by 4 without a remainder, so 4 is not a divisor of 9)
9:5 = 1 (4 left)
(9 is not divided by 5 without a remainder, so 5 is not a divisor of 9)
9: 6 = 1 (3 left)
(9 did not divide by 6 without a remainder, so 6 is not a divisor of 9)
9:7 = 1 (2 left)
(9 is not divided by 7 without a remainder, so 7 is not a divisor of 9)
9:8 = 1 (1 left)
(9 is not divided by 8 without a remainder, so 8 is not a divisor of 9)
9: 9 = 1
(9 divided by 9 without a remainder, so 9 is a divisor of 9)
Now write down the divisors of both numbers. The numbers highlighted in blue are the divisors. Let's write them out:
Having written out the divisors, you can immediately determine which one is the largest and most common.
By definition, the greatest common divisor of 12 and 9 is the number by which 12 and 9 are evenly divisible. The greatest and common divisor of the numbers 12 and 9 is the number 3
Both the number 12 and the number 9 are divisible by 3 without a remainder:
So gcd (12 and 9) = 3
The second way to find GCD
Now consider the second way to find the greatest common divisor. The essence of this method is to decompose both numbers into prime factors and multiply the common ones.
Example 1. Find GCD of numbers 24 and 18
First, let's factor both numbers into prime factors:
Now we multiply their common factors. In order not to get confused, the common factors can be underlined.
We look at the decomposition of the number 24. Its first factor is 2. We are looking for the same factor in the decomposition of the number 18 and see that it is also there. We underline both twos:
Again we look at the decomposition of the number 24. Its second factor is also 2. We are looking for the same factor in the decomposition of the number 18 and see that it is not there for the second time. Then we don't highlight anything.
The next two in the expansion of the number 24 is also missing in the expansion of the number 18.
We pass to the last factor in the decomposition of the number 24. This is the factor 3. We are looking for the same factor in the decomposition of the number 18 and see that it is also there. We emphasize both threes:
So, the common factors of the numbers 24 and 18 are the factors 2 and 3. To get the GCD, these factors must be multiplied:
So gcd (24 and 18) = 6
The third way to find GCD
Now consider the third way to find the greatest common divisor. The essence of this method lies in the fact that the numbers to be searched for the greatest common divisor are decomposed into prime factors. Then, from the decomposition of the first number, factors that are not included in the decomposition of the second number are deleted. The remaining numbers in the first expansion are multiplied and get GCD.
For example, let's find the GCD for the numbers 28 and 16 in this way. First of all, we decompose these numbers into prime factors:
We got two expansions: and
Now, from the expansion of the first number, we delete the factors that are not included in the expansion of the second number. The expansion of the second number does not include seven. We will delete it from the first expansion:
Now we multiply the remaining factors and get the GCD:
The number 4 is the greatest common divisor of the numbers 28 and 16. Both of these numbers are divisible by 4 without a remainder:
Example 2 Find GCD of numbers 100 and 40
Factoring out the number 100
Factoring out the number 40
We got two expansions:
Now, from the expansion of the first number, we delete the factors that are not included in the expansion of the second number. The expansion of the second number does not include one five (there is only one five). We delete it from the first decomposition
Multiply the remaining numbers:
We got the answer 20. So the number 20 is the greatest common divisor of the numbers 100 and 40. These two numbers are divisible by 20 without a remainder:
GCD (100 and 40) = 20.
Example 3 Find the gcd of the numbers 72 and 128
Factoring out the number 72
Factoring out the number 128
2×2×2×2×2×2×2
Now, from the expansion of the first number, we delete the factors that are not included in the expansion of the second number. The expansion of the second number does not include two triplets (there are none at all). We delete them from the first expansion:
We got the answer 8. So the number 8 is the greatest common divisor of the numbers 72 and 128. These two numbers are divisible by 8 without a remainder:
GCD (72 and 128) = 8
Finding GCD for Multiple Numbers
The greatest common divisor can be found for several numbers, and not just for two. For this, the numbers to be searched for the greatest common divisor are decomposed into prime factors, then the product of the common prime factors of these numbers is found.
For example, let's find the GCD for the numbers 18, 24 and 36
Factoring the number 18
Factoring the number 24
Factoring the number 36
We got three expansions:
Now we select and underline the common factors in these numbers. Common factors must be included in all three numbers:
We see that the common factors for the numbers 18, 24 and 36 are factors 2 and 3. By multiplying these factors, we get the GCD we are looking for:
We got the answer 6. So the number 6 is the greatest common divisor of the numbers 18, 24 and 36. These three numbers are divisible by 6 without a remainder:
GCD (18, 24 and 36) = 6
Example 2 Find gcd for numbers 12, 24, 36 and 42
Let's factorize each number. Then we find the product of the common factors of these numbers.
Factoring the number 12
Factoring the number 42
We got four expansions:
Now we select and underline the common factors in these numbers. Common factors must be included in all four numbers:
We see that the common factors for the numbers 12, 24, 36, and 42 are the factors 2 and 3. By multiplying these factors, we get the GCD we are looking for:
We got the answer 6. So the number 6 is the greatest common divisor of the numbers 12, 24, 36 and 42. These numbers are divisible by 6 without a remainder:
gcd(12, 24, 36 and 42) = 6
From the previous lesson, we know that if some number is divided by another without a remainder, it is called a multiple of this number.
It turns out that a multiple can be common to several numbers. And now we will be interested in a multiple of two numbers, while it should be as small as possible.
Definition. Least common multiple (LCM) of numbers a And b- a And b a and number b.
Definition contains two variables a And b. Let's substitute any two numbers for these variables. For example, instead of a variable a substitute the number 9, and instead of the variable b let's substitute the number 12. Now let's try to read the definition:
Least common multiple (LCM) of numbers 9 And 12 - is the smallest number that is a multiple of 9 And 12 . In other words, it is such a small number that is divisible without a remainder by the number 9 and on the number 12 .
It is clear from the definition that the LCM is the smallest number that is divisible without a remainder by 9 and 12. This LCM is required to be found.
There are two ways to find the least common multiple (LCM). The first way is that you can write down the first multiples of two numbers, and then choose among these multiples such a number that will be common to both numbers and small. Let's apply this method.
First of all, let's find the first multiples for the number 9. To find the multiples for 9, you need to multiply this nine by the numbers from 1 to 9 in turn. The answers you get will be multiples of the number 9. So, let's start. Multiples will be highlighted in red:
Now we find multiples for the number 12. To do this, we multiply 12 by all the numbers 1 to 12 in turn.
Numbers that are divisible by 10 are called multiples of 10. For example, 30 or 50 are multiples of 10. 28 is a multiple of 14. Numbers that are divisible by both 10 and 14 are naturally called common multiples of 10 and 14.
We can find any number of common multiples. For example, 140, 280, etc.
The natural question is: how to find the least common multiple, the least common multiple?
Of the multiples found for 10 and 14, the smallest so far is 140. But is it the least common multiple?
Let's factor our numbers:
Let's construct a number that is divisible by 10 and 14. To be divisible by 10, you need to have factors 2 and 5. To be divisible by 14, you need to have factors 2 and 7. But 2 is already there, it remains to add 7. The resulting number 70 is the common multiple of 10 and 14. In this case, it will not be possible to construct a number less than this so that it is also a common multiple.
So this is what it is least common multiple. We use the notation LCM for it.
Let's find GCD and LCM for numbers 182 and 70.
Calculate yourself:
3. 
We check:
To understand what GCD and LCM are, one cannot do without factoring. But, when we already understood what it is, it is no longer necessary to factor it every time.
For example:
You can easily see that for two numbers where one is divisible by the other, the smaller one is their GCD and the larger one is their LCM. Try to explain why this is so.
Dad's step length is 70 cm, and the little daughter's step is 15 cm. They start walking with their feet on the same mark. How far will they walk before their feet are level again?
Dad and daughter start moving. First, the legs are on the same mark. After walking a few steps, their legs again stood on the same mark. This means that both dad and daughter got a whole number of steps to this mark. This means that the distance to her should be divided by the step length of both dad and daughter.
That is, we must find:
That is, it will happen in 210 cm = 2 m 10 cm.
It is easy to understand that the father will take 3 steps, and the daughter - 14 (Fig. 1).
Rice. 1. Illustration for the problem
Task 1
Petya has 100 friends on VKontakte, and Vanya has 200. How many friends does Petya and Vanya have together if there are 30 friends in common?
Answer 300 is incorrect, because they may have mutual friends.
Let's solve this problem like this. Let's depict the set of all Petya's friends around. Let's depict many of Vanya's friends in a different circle, more.
These circles have a common part. There are common friends there. This common part is called the "intersection" of the two sets. That is, the set of mutual friends is the intersection of the sets of friends of each.
Rice. 2. Circles of many friends
If there are 30 common friends, then on the left 70 are only Petina's friends, and 170 are Vanina's only (see Fig. 2).
How much?
An entire large set consisting of two circles is called the union of the two sets.
In fact, VK itself solves the problem of crossing two sets for us, it immediately indicates a lot of mutual friends when you go to the page of another person.
The situation with GCD and LCM of two numbers is very similar.
Task 2
Consider two numbers: 126 and 132.
We will depict their prime factors in circles (see Fig. 3).
Rice. 3. Circles with prime factors
The intersection of sets are common divisors. Of these, NOD consists.
The union of the two sets gives us the LCM.
Bibliography
1. Vilenkin N.Ya., Zhokhov V.I., Chesnokov A.S., Shvartsburd S.I. Mathematics 6. - M.: Mnemosyne, 2012.
2. Merzlyak A.G., Polonsky V.V., Yakir M.S. Mathematics 6th grade. - Gymnasium. 2006.
3. Depman I.Ya., Vilenkin N.Ya. Behind the pages of a mathematics textbook. - M.: Enlightenment, 1989.
4. Rurukin A.N., Chaikovsky I.V. Tasks for the course of mathematics grade 5-6. - M.: ZSh MEPhI, 2011.
5. Rurukin A.N., Sochilov S.V., Chaikovsky K.G. Mathematics 5-6. A manual for students of the 6th grade of the MEPhI correspondence school. - M.: ZSh MEPhI, 2011.
6. Shevrin L.N., Gein A.G., Koryakov I.O., Volkov M.V. Mathematics: Textbook-interlocutor for 5-6 grades of high school. - M .: Education, Mathematics Teacher Library, 1989.
3. Website "School Assistant" ()
Homework
1. 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?
2. Find the LCM of numbers:
3. Find the prime factors of the least common multiple of numbers:
And if: 
, , .
Loading...