We call numbers that are divisible by 10 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: Interlocutor textbook for grades 5-6 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: 
, , .
largest 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)$
Remember!
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.
For example:
- 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.
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.
Remember!
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 a remainder.
Remember!
Greatest Common Divisor(GCD) of two given numbers "a" and "b" - this is the largest number by which both numbers "a" and "b" are divided without a remainder.
Briefly, the greatest common divisor of the numbers "a" and "b" is written as follows:
gcd (a; b) .
Example: gcd (12; 36) = 12 .
The divisors of numbers in the notation of the solution denote capital letter"D".
D(7) = (1, 7)
D(9) = (1, 9)
gcd (7; 9) = 1
The numbers 7 and 9 have only one common divisor - the number 1. Such numbers are called coprime numbers.
Remember!
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:
- decompose the divisors of numbers into prime factors;
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 764 = 2 2 2 2 2 2
- We find the product of identical prime factors and write down the answer;
GCD (28; 64) = 2 2 = 4Answer: 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”.
Finding the greatest common divisor of three and more numbers can be reduced to sequentially finding the gcd of two numbers. We mentioned this when studying the properties of GCD. There we formulated and proved the theorem: the greatest common divisor of several numbers a 1 , a 2 , …, a k is equal to the number dk, which is found in the sequential calculation GCD(a 1 , a 2)=d 2, GCD(d 2 , a 3)=d 3, GCD(d 3 , a 4)=d 4, …,GCD(d k-1 , a k)=d k.
Let's see how the process of finding the GCD of several numbers looks like by considering the solution of the example.
Example.
Find the greatest common divisor of four numbers 78 , 294 , 570 And 36 .
Solution.
In this example a 1 =78, a2=294, a 3 \u003d 570, a4=36.
First, using the Euclid algorithm, we determine the greatest common divisor d2 first two numbers 78 And 294 . When dividing, we get the equalities 294=78 3+60; 78=60 1+18;60=18 3+6 And 18=6 3. Thus, d 2 \u003d GCD (78, 294) \u003d 6.
Now let's calculate d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570). Let's use Euclid's algorithm again: 570=6 95, hence, d 3 \u003d GCD (6, 570) \u003d 6.
It remains to calculate d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36). Because 36 divided by 6 , That d 4 \u003d GCD (6, 36) \u003d 6.
So the greatest common divisor of the four given numbers is d4=6, that is, gcd(78, 294, 570, 36)=6.
Answer:
gcd(78, 294, 570, 36)=6.
Decomposing numbers into prime factors also allows you to calculate the GCD of three or more numbers. In this case, the greatest common divisor is found as the product of all common prime factors of the given numbers.
Example.
Calculate the GCD of the numbers from the previous example using their prime factorizations.
Solution.
Let's decompose the numbers 78 , 294 , 570 And 36 into prime factors, we get 78=2 3 13,294=2 3 7 7, 570=2 3 5 19, 36=2 2 3 3. The common prime factors of all given four numbers are the numbers 2 And 3 . Hence, GCD(78, 294, 570, 36)=2 3=6.
Answer:
gcd(78, 294, 570, 36)=6.
Top of page
Finding the gcd of negative numbers
If one, several or all of the numbers whose greatest divisor is to be found are negative numbers, then their gcd is equal to the greatest common divisor of the modules of these numbers. This is because opposite numbers a And -a have the same divisors, which we discussed when studying the properties of divisibility.
Example.
Find the gcd of negative integers −231 And −140 .
Solution.
The absolute value of a number −231 equals 231 , and the modulus of the number −140 equals 140 , And gcd(−231, −140)=gcd(231, 140). Euclid's algorithm gives us the following equalities: 231=140 1+91; 140=91 1+49; 91=49 1+42; 49=42 1+7 And 42=7 6. Hence, gcd(231, 140)=7. Then the desired greatest common divisor of negative numbers −231 And −140 equals 7 .
Answer:
GCD(−231,−140)=7.
Example.
Determine the gcd of three numbers −585 , 81 And −189 .
Solution.
Finding the greatest common divisor negative numbers can be replaced by their absolute values, that is, gcd(−585, 81, −189)=gcd(585, 81, 189). Number expansions 585 , 81 And 189 into prime factors are, respectively, of the form 585=3 3 5 13, 81=3 3 3 3 And 189=3 3 3 7. The common prime factors of these three numbers are 3 And 3 . Then GCD(585, 81, 189)=3 3=9, hence, gcd(−585, 81, −189)=9.
Answer:
gcd(−585, 81, −189)=9.
35. Roots of a polynomial. Bezout's theorem. (33 and up)
36. Multiple roots, criterion of multiplicity of the root.
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) We write out all the common divisors of numbers (36; 24) and select in green the largest, this will be the greatest common divisor of GCD 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. Find the missing factors, highlight in blue in the expansion of the smaller number the factors that were not included in the expansion more.
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
