GCD is the greatest common divisor.
To find the greatest common divisor of several numbers:
- determine the factors common to both numbers;
- find the product of common factors.
An example of finding a GCD:
Find the GCD of the numbers 315 and 245.
315 = 5 * 3 * 3 * 7;
245 = 5 * 7 * 7.
2. Write out the factors common to both numbers:
3. Find the product of common factors:
gcd(315; 245) = 5 * 7 = 35.
Answer: GCD(315; 245) = 35.
Finding the NOC
LCM is the least common multiple.
To find the least common multiple of several numbers:
- decompose numbers into prime factors;
- write out the factors included in the expansion of one of the numbers;
- add to them the missing factors from the expansion of the second number;
- find the product of the resulting factors.
An example of finding the NOC:
Find the LCM of the numbers 236 and 328:
1. We decompose the numbers into prime factors:
236 = 2 * 2 * 59;
328 = 2 * 2 * 2 * 41.
2. Write down the factors included in the expansion of one of the numbers and add to them the missing factors from the expansion of the second number:
2; 2; 59; 2; 41.
3. Find the product of the resulting factors:
LCM(236; 328) = 2 * 2 * 59 * 2 * 41 = 19352.
Answer: LCM(236; 328) = 19352.
To find the GCD (greatest common divisor) of two numbers, you need:
2. Find (underline) all common prime factors in the obtained expansions.
3. Find the product of common prime factors.
To find the LCM (least common multiple) of two numbers, you need:
1. Decompose these numbers into prime factors.
2. Supplement the expansion of one of them with those factors of the expansion of the other number, which are not in the expansion of the first.
3. Calculate the product of the obtained factors.
Back forward
Attention! The slide preview is for informational purposes only and may not represent the full extent of the presentation. If you are interested this work please download the full version.
With the concepts of the greatest common divisor (GCD) and the least common multiple (LCM), high school students meet in the sixth grade. This topic is always difficult to master. Children often confuse these concepts, do not understand why they need to be studied. IN Lately and in the popular science literature there are separate statements that this material should be excluded from the school curriculum. I think that this is not entirely true, and you need to study it, if not in the classroom, then in after hours in the classroom, the school component is mandatory, as this contributes to the development of logical thinking of schoolchildren, increasing the speed of computational operations, and the ability to solve problems using beautiful methods.
When studying the topic "Addition and subtraction of fractions with different denominators"We teach children to find a common denominator of two or more numbers. For example, you need to add the fractions 1/3 and 1/5. Students can easily find a number that is divisible without a remainder by 3 and 5. This number is 15. Indeed, if the numbers are small, then their common denominator is easy to find, knowing the multiplication table well.Some of the guys notice that this number is the product of the numbers 3 and 5. The children have the opinion that you can always find a common denominator for numbers in this way.For example, we subtract the fractions 7/ 18 and 5 / 24. Let's find the product of the numbers 18 and 24. It is equal to 432. We already got a large number, and if you need to do some calculations further (especially for examples for all actions), then the probability of an error increases. common multiple of numbers (LCM), which in this case is equivalent to the least common denominator (LCD) - the number 72 - will greatly facilitate calculations and lead to a faster solution of the example, and thereby save time allotted for execution given task, which plays an important role in the performance of the final test, control works especially during the final assessment.
When studying the topic "Reduction of fractions", you can move successively dividing the numerator and denominator of the fraction by the same natural number, using the signs of divisibility of numbers, eventually obtaining an irreducible fraction. For example, you need to reduce the fraction 128/344. We first divide the numerator and denominator of the fraction by the number 2, we get the fraction 64/172. Once again, we divide the numerator and denominator of the resulting fraction by 2, we get the fraction 32/86. Divide once again the numerator and denominator of the fraction by 2, we get the irreducible fraction 16/43. But fraction reduction can be done much easier if we find the greatest common divisor of the numbers 128 and 344. GCD (128, 344) = 8. Dividing the numerator and denominator of the fraction by this number, we immediately get an irreducible fraction.
Gotta show the kids different ways finding the greatest common divisor (GCD) and the least common multiple (LCM) of numbers. In simple cases, it is convenient to find the greatest common divisor (GCD) and least common multiple (LCM) of numbers by simple enumeration. As the numbers get larger, prime factors can be used. The sixth grade textbook (author N.Ya. Vilenkin) shows the following method for finding the greatest common divisor (GCD) of numbers. Let's decompose the numbers into prime factors:
- 16 = 2*2*2*2
- 120 = 2*2*2*3*5
Then, from the factors included in the expansion of one of these numbers, we cross out those that are not included in the expansion of the other number. The product of the remaining factors will be the greatest common divisor of these numbers. In this case, this number is 8. From my own experience, I was convinced that it is more understandable for children if we underline the same factors in the expansions of numbers, and then in one of the expansions we find the product of the underlined factors. This is the greatest common divisor of these numbers. In the sixth grade, children are active and inquisitive. You can set them the following task: try to find the greatest common divisor of the numbers 343 and 287 in the described way. It is not immediately clear how to factor them into prime factors. And here you can tell them about the wonderful method invented by the ancient Greeks, which allows you to search for the greatest common divisor (GCD) without decomposing into prime factors. This method of finding the greatest common divisor was first described in Euclid's Elements. It is called the Euclid algorithm. It consists in the following: First, divide the larger number by the smaller one. If there is a remainder, then divide the smaller number by the remainder. If the remainder is obtained again, then divide the first remainder by the second. So continue to divide until the remainder is zero. The last divisor is the greatest common divisor (GCD) of these numbers.
Let's return to our example and, for clarity, write the solution in the form of a table.
| Dividend | Divider | Private | Remainder |
| 343 | 287 | 1 | 56 |
| 287 | 56 | 5 | 7 |
| 56 | 7 | 8 | 0 |
So gcd(344,287) = 7
And how to find the least common multiple (LCM) of the same numbers? Is there some way for this that does not require a preliminary decomposition of these numbers into prime factors? It turns out there is, and a very simple one at that. We need to multiply these numbers and divide the product by the greatest common divisor (GCD) we found. In this example, the product of the numbers is 98441. Divide it by 7 and get the number 14063. LCM(343,287) = 14063.
One of the difficult topics in mathematics is the solution of word problems. It is necessary to show students how using the concepts of "Greatest Common Divisor (GCD)" and "Least Common Multiple (LCM)" you can solve problems that are sometimes difficult to solve in the usual way. Here it is appropriate to consider with students, along with the tasks proposed by the authors of the school textbook, old and entertaining tasks that develop children's curiosity and increase interest in studying this topic. Skillful possession of these concepts allows students to see a beautiful solution to a non-standard problem. And if the child’s mood rises after solving a good problem, this is a sign of successful work.
Thus, the study at school of such concepts as "Greatest Common Divisor (GCD)" and "Least Common Multiple (LCD)" of numbers
Allows you to save time allotted for the execution of work, which leads to a significant increase in the volume of completed tasks;
Increases the speed and accuracy of performing arithmetic operations, which leads to a significant reduction in the number of allowable computational errors;
Allows you to find beautiful ways solving non-standard text problems;
Develops the curiosity of students, broadens their horizons;
Creates the prerequisites for the education of a versatile creative personality.
Finding the greatest common divisor of three or more numbers can be reduced to successively 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 d k, 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. In this way, 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, Consequently, 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 , then d 4 \u003d GCD (6, 36) \u003d 6.
So the greatest common divisor of the four given numbers is d4=6, i.e, 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 . Consequently, 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 numbers, largest divisor 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. Consequently, 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, Consequently, 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.
Definition. The largest natural number by which the numbers a and b are divisible without a remainder is called greatest common divisor (gcd) these numbers.
Let's find the greatest common divisor of the numbers 24 and 35.
The divisors of 24 will be the numbers 1, 2, 3, 4, 6, 8, 12, 24, and the divisors of 35 will be the numbers 1, 5, 7, 35.
We see that the numbers 24 and 35 have only one common divisor - the number 1. Such numbers are called coprime.
Definition. The natural numbers are called coprime if their greatest common divisor (gcd) is 1.
Greatest Common Divisor (GCD) can be found without writing out all the divisors of the given numbers.
Factoring the numbers 48 and 36, we get:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
From the factors included in the expansion of the first of these numbers, we delete those that are not included in the expansion of the second number (i.e., two deuces).
The factors 2 * 2 * 3 remain. Their product is 12. This number is the greatest common divisor of the numbers 48 and 36. The greatest common divisor of three or more numbers is also found.
To find greatest common divisor
2) from the factors included in the expansion of one of these numbers, cross out those that are not included in the expansion of other numbers;
3) find the product of the remaining factors.
If all given numbers are divisible by one of them, then this number is greatest common divisor given numbers.
For example, the greatest common divisor of 15, 45, 75, and 180 is 15, since it divides all other numbers: 45, 75, and 180.
Least common multiple (LCM)
Definition. Least common multiple (LCM) natural numbers a and b are the smallest natural number that is a multiple of both a and b. The least common multiple (LCM) of the numbers 75 and 60 can be found without writing out multiples of these numbers in a row. To do this, we decompose 75 and 60 into simple factors: 75 \u003d 3 * 5 * 5, and 60 \u003d 2 * 2 * 3 * 5.
Let's write out the factors included in the expansion of the first of these numbers, and add to them the missing factors 2 and 2 from the expansion of the second number (i.e., we combine the factors).
We get five factors 2 * 2 * 3 * 5 * 5, the product of which is 300. This number is the least common multiple of the numbers 75 and 60.
Also find the least common multiple of three or more numbers.
To find the least common multiple several natural numbers, you need:
1) decompose them into prime factors;
2) write out the factors included in the expansion of one of the numbers;
3) add to them the missing factors from the expansions of the remaining numbers;
4) find the product of the resulting factors.
Note that if one of these numbers is divisible by all other numbers, then this number is the least common multiple of these numbers.
For example, the least common multiple of 12, 15, 20, and 60 would be 60, since it is divisible by all given numbers.
Pythagoras (VI century BC) and his students studied the issue of divisibility of numbers. A number equal to the sum of all its divisors (without the number itself), they called the perfect number. For example, the numbers 6 (6 = 1 + 2 + 3), 28 (28 = 1 + 2 + 4 + 7 + 14) are perfect. The next perfect numbers are 496, 8128, 33,550,336. The Pythagoreans knew only the first three perfect numbers. The fourth - 8128 - became known in the 1st century. n. e. The fifth - 33 550 336 - was found in the 15th century. By 1983, 27 perfect numbers were already known. But until now, scientists do not know whether there are odd perfect numbers, whether there is the largest perfect number.
The interest of ancient mathematicians in prime numbers is due to the fact that any number is either prime or can be represented as a product prime numbers, i.e., prime numbers are, as it were, bricks from which the rest of the natural numbers are built.
You probably noticed that prime numbers in the series of natural numbers occur unevenly - in some parts of the series there are more of them, in others - less. But the further we move along the number series, the rarer the prime numbers. The question arises: does the last (largest) prime number exist? The ancient Greek mathematician Euclid (3rd century BC), in his book "Beginnings", which for two thousand years was the main textbook of mathematics, proved that there are infinitely many prime numbers, that is, behind each prime number there is an even greater prime number.
To find prime numbers, another Greek mathematician of the same time, Eratosthenes, came up with such a method. He wrote down all the numbers from 1 to some number, and then crossed out the unit, which is neither a prime nor a composite number, then crossed out through one all the numbers after 2 (numbers that are multiples of 2, i.e. 4, 6 , 8, etc.). The first remaining number after 2 was 3. Then, after two, all the numbers after 3 were crossed out (numbers that are multiples of 3, i.e. 6, 9, 12, etc.). in the end, only the prime numbers remained uncrossed out.
Many divisors
Consider the following problem: find the divisor of the number 140. It is obvious that the number 140 has not one divisor, but several. In such cases, the task is said to have lots of solutions. Let's find them all. First of all, we decompose this number into prime factors:
140 = 2 ∙ 2 ∙ 5 ∙ 7.
Now we can easily write out all the divisors. Let's start with simple divisors, that is, those that are present in the expansion above:
Then we write out those that are obtained by pairwise multiplication of prime divisors:
2∙2 = 4, 2∙5 = 10, 2∙7 = 14, 5∙7 = 35.
Then - those that contain three simple divisors:
2∙2∙5 = 20, 2∙2∙7 = 28, 2∙5∙7 = 70.
Finally, let's not forget the unit and the decomposable number itself:
All divisors found by us form lots of divisors of the number 140, which is written using curly braces:
The set of divisors of the number 140 =
{1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140}.
For convenience of perception, we have written out the divisors here ( set elements) in ascending order, but generally speaking, this is not necessary. In addition, we introduce an abbreviation. Instead of "The set of divisors of the number 140" we will write "D (140)". In this way,
Similarly, one can find the set of divisors for any other natural number. For example, from the expansion
105 = 3 ∙ 5 ∙ 7
we get:
D(105) = (1, 3, 5, 7, 15, 21, 35, 105).
From the set of all divisors, one should distinguish the set of prime divisors, which for the numbers 140 and 105 are equal, respectively:
PD(140) = (2, 5, 7).
PD(105) = (3, 5, 7).
It should be emphasized that in the decomposition of the number 140 into prime factors, two is present twice, while in the set PD(140) it is only one. The set of PD(140) is, in essence, all the answers to the problem: "Find a prime factor of the number 140". It is clear that the same answer should not be repeated more than once.
Fraction reduction. Greatest Common Divisor
Consider a fraction
We know that this fraction can be reduced by a number that is both a divisor of the numerator (105) and a divisor of the denominator (140). Let's look at the sets D(105) and D(140) and write down their common elements.
D(105) = (1, 3, 5, 7, 15, 21, 35, 105);
D(140) = (1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140).
Common elements of the sets D(105) and D(140) =
The last equality can be written shorter, namely:
D(105) ∩ D(140) = (1, 5, 7, 35).
Here, the special icon "∩" ("bag with the hole down") just indicates that from the two sets written on opposite sides of it, only common elements should be selected. The entry "D (105) ∩ D (140)" reads " intersection sets of Te from 105 and Te from 140.
[Note along the way that you can perform various binary operations with sets, almost like with numbers. Another common binary operation is Union, which is indicated by the icon "∪" ("bag with the hole up"). The union of two sets includes all the elements of both sets:
PD(105) = (3, 5, 7);
PD(140) = (2, 5, 7);
PD(105) ∪ PD(140) = (2, 3, 5, 7). ]
So, we found out that the fraction
can be reduced to any of the numbers belonging to the set
D(105) ∩ D(140) = (1, 5, 7, 35)
and cannot be reduced by any other natural number. That's all possible ways reductions (except for the uninteresting reduction by one):
It is obvious that it is most practical to reduce the fraction by a number, if possible, a larger one. IN this case is the number 35, which is said to be greatest common divisor (GCD) numbers 105 and 140. This is written as
gcd(105, 140) = 35.
However, in practice, if we are given two numbers and need to find their greatest common divisor, we do not have to build any sets at all. It is enough to simply factorize both numbers into prime factors and underline those of these factors that are common to both factorizations, for example:
105 = 3 ∙ 5 ∙ 7 ;
140 = 2 ∙ 2 ∙ 5 ∙ 7 .
Multiplying the underlined numbers (in any of the expansions), we get:
gcd(105, 140) = 5 ∙ 7 = 35.
Of course, it is possible that there are more than two underlined factors:
168 = 2 ∙ 2 ∙ 2 ∙ 3 ∙ 7;
396 = 2 ∙ 2 ∙ 3 ∙ 3 ∙ 11.
From here it is clear that
gcd(168, 396) = 2 ∙ 2 ∙ 3 = 12.
Special mention deserves the situation when there are no common factors at all and there is nothing to emphasize, for example:
42 = 2 ∙ 3 ∙ 7;
In this case,
gcd(42, 55) = 1.
Two natural numbers for which the gcd is equal to one are called coprime. If you make a fraction from such numbers, for example,
then such a fraction is irreducible.
Generally speaking, the rule for reducing fractions can be written as follows:
|
a/ gcd( a, b) |
|||
|
b/ gcd( a, b) |
Here it is assumed that a And b are natural numbers, and all fractions are positive. If we now assign a minus sign to both sides of this equality, we get the corresponding rule for negative fractions.
Addition and subtraction of fractions. Least common multiple
Suppose you want to calculate the sum of two fractions:
We already know how denominators are decomposed into prime factors:
105 = 3 ∙ 5 ∙ 7 ;
140 = 2 ∙ 2 ∙ 5 ∙ 7 .
It immediately follows from this expansion that, in order to reduce the fractions to common denominator, it is enough to multiply the numerator and denominator of the first fraction by 2 ∙ 2 (the product of the unstressed prime factors of the second denominator), and the numerator and denominator of the second fraction by 3 (“the product” of the unstressed prime factors of the first denominator). As a result, the denominators of both fractions will become equal to a number that can be represented as follows:
2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 = 105 ∙ 2 ∙ 2 = 140 ∙ 3 = 420.
It is easy to see that both original denominators (both 105 and 140) are divisors of the number 420, and the number 420, in turn, is a multiple of both denominators - and not just a multiple, it is least common multiple (NOC) numbers 105 and 140. This is written like this:
LCM(105, 140) = 420.
Looking more closely at the expansion of the numbers 105 and 140, we see that
105 ∙ 140 = LCM(105, 140) ∙ GCD(105, 140).
Similarly, for arbitrary natural numbers b And d:
b ∙ d= LCM( b, d) ∙ GCD( b, d).
Now let's complete the summation of our fractions:
|
3 ∙ 5 ∙ 7 |
2 ∙ 2 ∙ 5 ∙ 7 |
|
2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 |
2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 |
|
2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 |
|
2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 |
|
2 ∙ 2 ∙ 3 ∙ 5 |
|
Note. To solve some problems, you need to know what the square of a number is. Number square a called a number a multiplied by itself, that is a∙a. (As you can see, it is equal to the area of a square with a side a). |
Loading...