Who invented nok and nod. Common divisor and multiple

Many divisors

Let's consider the following problem: find the divisor of the number 140. Obviously, the number 140 has not one divisor, but several. In such cases the problem is said to have many decisions. Let's find them all. First of all, let's decompose given number on prime factors:

140 = 2 ∙ 2 ∙ 5 ∙ 7.

Now we can easily write down all the divisors. Let's start with prime factors, that is, those that are present in the expansion given above:

Then we write down 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 prime divisors:

2∙2∙5 = 20, 2∙2∙7 = 28, 2∙5∙7 = 70.

Finally, let’s not forget the unit and the decomposed number itself:

All the divisors we found form many divisors of the number 140, which is written using curly braces:

Set of divisors of the number 140 =

{1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140}.

For ease of perception, we have written down the divisors here ( elements of the set) in ascending order, but, generally speaking, this is not necessary. In addition, we introduce an abbreviation. Instead of “Set of divisors of the number 140” we will write “D(140)”. Thus,

In the same way, you can find the set of divisors for any other natural number. For example, from the decomposition

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 simple divisors, which for the numbers 140 and 105 are equal, respectively:

PD(140) = (2, 5, 7).

PD(105) = (3, 5, 7).

It should be especially emphasized that in the decomposition of the number 140 into prime factors, the two appears twice, while in the set PD(140) there is only one. The set of PD(140) is, in essence, all the answers to the problem: “Find the prime factor of the number 140.” It is clear that the same answer should not be repeated more than once.

Reducing fractions. Greatest common divisor

Consider the 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 them down 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 more briefly, namely:

D(105) ∩ D(140) = (1, 5, 7, 35).

Here the special icon “∩” (“bag with the hole down”) indicates that of the two sets written according to different sides from it, you need to select only common elements. The entry “D(105) ∩ D(140)” reads “ intersection sets of De from 105 and De from 140.”

[Note along the way that you can perform various binary operations with sets, almost like with numbers. Another common binary operation is association, which is indicated by the “∪” icon (“bag with the hole facing up”). The union of two sets includes all 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 by 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 abbreviations (except for the uninteresting abbreviation by one):

Obviously, it is most practical to reduce the fraction by a number that is as large as possible. IN in this case this 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 should not construct any sets at all. It is enough to simply decompose both numbers into prime factors and highlight those of these factors that are common to both decompositions, 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 will be more than two underlined factors:

168 = 2 ∙ 2 ∙ 2 ∙ 3 ∙ 7;

396 = 2 ∙ 2 ∙ 3 ∙ 3 ∙ 11.

From this it is clear that

gcd(168, 396) = 2 ∙ 2 ∙ 3 = 12.

The situation deserves special mention when common factors not 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 GCD equal to one, are called mutually prime. 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:

Here it is assumed that a And b are natural numbers, and the entire fraction is positive. If we now add a minus sign to both sides of this equality, we obtain the corresponding rule for negative fractions.

Adding and subtracting fractions. Least common multiple

Suppose you need to calculate the sum of two fractions:

We already know how the denominators are factored into prime factors:

105 = 3 ∙ 5 ∙ 7 ;

140 = 2 ∙ 2 ∙ 5 ∙ 7 .

From this expansion it immediately follows that, in order to reduce fractions to common denominator, it is enough to multiply the numerator and denominator of the first fraction by 2 ∙ 2 (the product of the unemphasized prime factors of the second denominator), and the numerator and denominator of the second fraction by 3 (the “product” of the unemphasized prime factors of the first denominator). As a result, the denominators of both fractions will become equal to the number, which 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. It is written like this:

LCM(105, 140) = 420.

Taking a closer look at the decomposition of the numbers 105 and 140, we see that

105 ∙ 140 = GCD(105, 140) ∙ GCD(105, 140).

Similarly, for arbitrary natural numbers b And d:

b ∙ d= LOC( b, d) ∙ GCD( b, d).

Now let's complete the summation of our fractions:

Greatest common divisor and least common multiple are key arithmetic concepts, which allow you to operate effortlessly ordinary fractions. LCM and are most often used to find the common denominator of several fractions.

Basic Concepts

The divisor of an integer X is another integer Y by which X is divided without leaving a remainder. For example, the divisor of 4 is 2, and 36 is 4, 6, 9. A multiple of an integer X is a number Y that is divisible by X without a remainder. For example, 3 is a multiple of 15, and 6 is a multiple of 12.

For any pair of numbers we can find their common divisors and multiples. For example, for 6 and 9, the common multiple is 18, and the common divisor is 3. Obviously, pairs can have several divisors and multiples, so the calculations use the largest divisor GCD and the smallest multiple LCM.

The least divisor is meaningless, since for any number it is always one. The greatest multiple is also meaningless, since the sequence of multiples goes to infinity.

Finding gcd

There are many methods for finding the greatest common divisor, the most famous of which are:

• sequential search of divisors, selection of common ones for a pair and search for the largest of them;
• decomposition of numbers into indivisible factors;
• Euclidean algorithm;
• binary algorithm.

Today at educational institutions The most popular are the methods of prime factorization and the Euclidean algorithm. The latter, in turn, is used when solving Diophantine equations: searching for GCD is required to check the equation for the possibility of resolution in integers.

Finding the NOC

The least common multiple is also determined by sequential enumeration or factorization into indivisible factors. In addition, it is easy to find the LCM if the greatest divisor has already been determined. For numbers X and Y, the LCM and GCD are related by the following relationship:

LCD(X,Y) = X × Y / GCD(X,Y).

For example, if GCM(15,18) = 3, then LCM(15,18) = 15 × 18 / 3 = 90. The most obvious example of using LCM is to find the common denominator, which is the least common multiple of given fractions.

Coprime numbers

If a pair of numbers has no common divisors, then such a pair is called coprime. The gcd for such pairs is always equal to one, and based on the connection between divisors and multiples, the gcd for coprime pairs is equal to their product. For example, the numbers 25 and 28 are relatively prime, because they have no common divisors, and LCM(25, 28) = 700, which corresponds to their product. Any two indivisible numbers will always be relatively prime.

Common divisor and multiple calculator

Using our calculator you can calculate GCD and LCM for an arbitrary number of numbers to choose from. Tasks on calculating common divisors and multiples are found in grades 5 and 6 arithmetic, but GCD and LCM are key concepts mathematics and are used in number theory, planimetry and communicative algebra.

Real life examples

Common denominator of fractions

Least common multiple is used when finding the common denominator of several fractions. Let in arithmetic problem you need to sum 5 fractions:

1/8 + 1/9 + 1/12 + 1/15 + 1/18.

To add fractions, the expression must be reduced to a common denominator, which reduces to the problem of finding the LCM. To do this, select 5 numbers in the calculator and enter the values ​​of the denominators in the appropriate cells. The program will calculate the LCM (8, 9, 12, 15, 18) = 360. Now you need to calculate additional factors for each fraction, which are defined as the ratio of the LCM to the denominator. So the additional multipliers would look like:

• 360/8 = 45
• 360/9 = 40
• 360/12 = 30
• 360/15 = 24
• 360/18 = 20.

After this, we multiply all the fractions by the corresponding additional factor and get:

45/360 + 40/360 + 30/360 + 24/360 + 20/360.

We can easily sum such fractions and get the result as 159/360. We reduce the fraction by 3 and see the final answer - 53/120.

Solving linear Diophantine equations

Linear Diophantine equations are expressions of the form ax + by = d. If the ratio d / gcd(a, b) is an integer, then the equation is solvable in integers. Let's check a couple of equations to see if they have an integer solution. First, let's check the equation 150x + 8y = 37. Using a calculator, we find GCD (150.8) = 2. Divide 37/2 = 18.5. The number is not an integer, therefore the equation does not have integer roots.

Let's check the equation 1320x + 1760y = 10120. Use a calculator to find GCD(1320, 1760) = 440. Divide 10120/440 = 23. As a result, we get an integer, therefore, the Diophantine equation is solvable in integer coefficients.

Conclusion

GCD and LCM play a big role in number theory, and the concepts themselves are widely used in the most different areas mathematics. Use our calculator to calculate greatest divisors and least multiples of any number of numbers.

One of the tasks that poses a problem for modern schoolchildren, who are accustomed to using calculators built into gadgets both appropriately and inappropriately, is finding the greatest common divisor (GCD) of two or more numbers.

It is impossible to solve any math problem, if it is not known what they are actually asking about. To do this you need to know what this or that expression means., used in mathematics.

Need to know:

1. If a certain number can be used for counting various items, for example, nine pillars, sixteen houses, then it is natural. The smallest of them will be one.
2. When a natural number is divisible by another natural number, it is said to be smaller number is a divisor of the larger one.
3. If two or more different numbers are divisible by a certain number without a remainder, then they say that the latter will be their common divisor (CD).
4. The largest of the ODs is called the greatest common divisor (GCD).
5. In this case, when a number has only two natural divisors (itself and one), it is called prime. The smallest among them is two, and it is also the only even number in their series.
6. If two numbers have a maximum common divisor of one, then they will be relatively prime.
7. A number that has more than two divisors is called composite.
8. The process when all the prime factors are found, which when multiplied together will give in the product initial value in mathematics is called factorization. Moreover, identical factors in the expansion can appear more than once.

The following notations are accepted in mathematics:

1. Divisors D (45) = (1;3;5;9;45).
2. OD (8;18) = (1;2).
3. GCD (8;18) = 2.

Different ways to find GCD

The easiest way to answer the question is how to find gcd in the case where the smaller number is a divisor of the larger one. It will be in such a case greatest common divisor.

For example, GCD (15;45) = 15, GCD (48;24) = 24.

But such cases in mathematics are very rare, therefore, in order to find GCD, more complex techniques are used, although it is still highly recommended to check this option before starting work.

Method of decomposition into simple factors

If you need to find the gcd of two or more different numbers, it is enough to decompose each of them into simple factors, and then carry out the process of multiplying those of them that are present in each of the numbers.

Example 1

Let's look at how to find GCD 36 and 90:

1. 36 = 1*2*2*3*3;
2. 90 = 1*2*3*3*5;

GCD (36;90) = 1*2*3*3 = 18.

Now let's see how to find the same thing V case of three numbers, let's take 54 as an example; 162; 42.

We already know how to decompose 36, let’s figure out the rest:

1. 162 = 1*2*3*3*3*3;
2. 42 = 1*2*3*7;

Thus, gcd (36;162;42) = 1*2*3 = 6.

It should be noted that it is completely optional to write a unit in the expansion.

Let's consider a way how to simply factor into prime factors, to do this, we will write the number we need on the left, and on the right we will write simple divisors.

Columns can be separated using either a division sign or a simple vertical line.

1. 36 / 2 we will continue our division process;
2. 18/2 further;
3. 9/3 and again;
4. 3/3 is now quite elementary;
5. 1 - the result is ready.

Required 36 = 2*2*3*3.

Euclidean way

This option has been known to mankind since the time ancient Greek civilization, it is simpler in many ways, and is attributed to the great mathematician Euclid, although very similar algorithms were used earlier. This method is to use the following algorithm , we share larger number with the remainder for less. Then we divide our divisor by the remainder and continue to do this in a circle until a complete division occurs. Last value and turns out to be the desired greatest common divisor.

Here's an example of use of this algorithm :

Let's try to find out what GCD the 816 and 252 have:

1. 816 / 252 = 3 and the remainder is 60. Now we divide 252 by 60;
2. 252 / 60 = 4 the remainder this time will be 12. Let's continue our circular process, divide sixty by twelve;
3. 60 / 12 = 5. Since this time we did not receive any remainder, we have a ready result, twelve will be the value we are looking for.

So, at the end of our process we got gcd (816;252) = 12.

Actions if it is necessary to determine the GCD if more than two values ​​are specified

We have already figured out what to do in the case when there are two different numbers, now we will learn how to act if there are any 3 or more.

Despite all the apparent complexity, this task will no longer cause problems for us. Now we select any two numbers and determine the value we are looking for. The next step is to find the gcd of the obtained result and the third of set values. Then we again act according to the principle already known to us for the fourth fifth and so on.

Conclusion

So, despite the seemingly great complexity of the task initially set before us, in fact everything is simple, the main thing is to be able to carry out the division process accurately and adhere to any of the two algorithms described above.

Although both methods are quite acceptable, in secondary school the first method is much more often used. This is due to the fact that factorization into prime factors will be needed when studying the following educational topic- determination of the greatest common multiple (LCM). But it’s still worth noting once again that the use of the Euclidean algorithm cannot in any way be considered erroneous.

Video

With this video you can learn how to find the greatest common divisor.

Didn't get an answer to your question? Suggest a topic to the authors.

This article is about finding the greatest common divisor (GCD) two and more numbers. First, let's look at the Euclid algorithm; it allows you to find the gcd of two numbers. After this, we will focus on a method that allows us to calculate the gcd of numbers as the product of their common prime factors. Next, we will look at finding the greatest common divisor of three or more numbers, and also give examples of calculating the gcd of negative numbers.

Page navigation.

Euclidean algorithm for finding GCD

Note that if we had turned to the table of prime numbers from the very beginning, we would have found out that the numbers 661 and 113 are prime numbers, from which we could immediately say that their greatest common divisor is 1.

Answer:

GCD(661, 113)=1 .

Finding GCD by factoring numbers into prime factors

Let's consider another way to find GCD. The greatest common divisor can be found by factoring numbers into prime factors. Let's formulate a rule: GCD of two integers positive numbers a and b equal to the product all common prime factors found in the prime factorizations of numbers a and b.

Let's give an example to explain the rule for finding GCD. Let us know the decompositions of the numbers 220 and 600 into prime factors, they have the form 220=2·2·5·11 and 600=2·2·2·3·5·5. The common prime factors involved in factoring the numbers 220 and 600 are 2, 2 and 5. Therefore, GCD(220, 600)=2·2·5=20.

Thus, if we factor the numbers a and b into prime factors and find the product of all their common factors, then this will find the greatest common divisor of the numbers a and b.

Let's consider an example of finding GCD according to the stated rule.

Example.

Find the greatest common divisor of the numbers 72 and 96.

Solution.

Let's factor the numbers 72 and 96 into prime factors:

That is, 72=2·2·2·3·3 and 96=2·2·2·2·2·3. Common prime factors are 2, 2, 2 and 3. Thus, GCD(72, 96)=2·2·2·3=24.

Answer:

GCD(72, 96)=24 .

In conclusion of this paragraph, we note that the validity of the above rule for finding GCD follows from the property of the greatest common divisor, which states that GCD(m a 1 , m b 1)=m GCD(a 1 , b 1), where m is any positive integer.

Finding the gcd of three or more numbers

Finding the greatest common divisor of three or more numbers can be reduced to sequential finding 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 equal to the number d k , which is found by sequentially calculating 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 what the process of finding the gcd of several numbers looks like by looking at the solution to the example.

Example.

Find the greatest common factor of four numbers 78, 294, 570 and 36.

Solution.

In this example, a 1 =78, a 2 =294, a 3 =570, a 4 =36.

First, using the Euclidean algorithm, we determine the greatest common divisor d 2 of the first two numbers 78 and 294. When dividing, we obtain the equalities 294=78·3+60; 78=60·1+18 ; 60=18·3+6 and 18=6·3. Thus, d 2 =GCD(78, 294)=6.

Now let's calculate d 3 =GCD(d 2, a 3)=GCD(6, 570). Let's apply the Euclidean algorithm again: 570=6·95, therefore, d 3 = GCD(6, 570)=6.

It remains to calculate d 4 =GCD(d 3, a 4)=GCD(6, 36). Since 36 is divisible by 6, then d 4 = GCD(6, 36) = 6.

Thus, the greatest common divisor of the four given numbers is d 4 =6, that is, gcd(78, 294, 570, 36)=6.

Answer:

GCD(78, 294, 570, 36)=6 .

Factoring 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 factor 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 these four numbers are numbers 2 and 3. Hence, GCD(78, 294, 570, 36)=2·3=6.

Key words of the summary:Natural numbers. Arithmetic operations over natural numbers. Divisibility of natural numbers. Simple and composite numbers. Factoring a natural number into prime factors. Signs of divisibility by 2, 3, 5, 9, 4, 25, 10, 11. Greatest common divisor (GCD), as well as least common multiple (LCD). Division with remainder.

Natural numbers- these are numbers that are used to count objects - 1, 2, 3, 4 , ... But the number 0 is not natural!

The set of natural numbers is denoted by N. Record "3 ∈ N" means that the number three belongs to the set of natural numbers, and the notation "0 ∉ N" means that the number zero does not belong to this set.

Decimal number system - positioning system radix 10 .

Arithmetic operations on natural numbers

For natural numbers the following actions are defined: addition, subtraction, multiplication, division, exponentiation, root extraction. The first four actions are arithmetic.

Let a, b and c be natural numbers, then

1. ADDITION. Term + Term = Sum

Properties of addition
1. Communicative a + b = b + a.
2. Conjunctive a + (b + c) = (a + b) + c.
3. a + 0= 0 + a = a.

2. SUBTRACT. Minuend - Subtrahend = Difference

Properties of Subtraction
1. Subtracting the sum from the number a - (b + c) = a - b - c.
2. Subtracting a number from the sum (a + b) - c = a + (b - c); (a + b) - c = (a - c) + b.
3. a - 0 = a.
4. a - a = 0.

3. MULTIPLICATION. Multiplier * Multiplier = Product

Properties of Multiplication
1. Communicative a*b = b*a.
2. Conjunctive a*(b*c) = (a*b)*c.
3. 1 * a = a * 1 = a.
4. 0 * a = a * 0 = 0.
5. Distribution (a + b) * c = ac + bc; (a - b) * c = ac - bc.

4. DIVISION. Dividend: Divisor = Quotient

Properties of division
1. a: 1 = a.
2. a: a = 1. You can't divide by zero!
3. 0: a= 0.

Procedure

1. First of all, the actions in parentheses.
2. Then multiplication, division.
3. And only at the end addition and subtraction.

Divisibility of natural numbers. Prime and composite numbers.

Divisor of a natural number A is the natural number to which A divided without remainder. Number 1 is a divisor of any natural number.

The natural number is called simple, if it only has two divisor: one and the number itself. For example, numbers 2, 3, 11, 23 - prime numbers.

A number that has more than two divisors is called composite. For example, the numbers 4, 8, 15, 27 are composite numbers.

Divisibility test works several numbers: if at least one of the factors is divisible by a certain number, then the product is also divisible by this number. Work 24 15 77 divided by 12 , since the multiplier of this number 24 divided by 12 .

Divisibility test for a sum (difference) numbers: if each term is divisible by a certain number, then the entire sum is divided by this number. If a: b And c: b, That (a + c) : b. What if a: b, A c not divisible by b, That a+c not divisible by a number b.

If a: c And c: b, That a: b. Based on the fact that 72:24 and 24:12, we conclude that 72:12.

Representation of a number as a product of powers of prime numbers is called factoring a number into prime factors.

Fundamental Theorem of Arithmetic: any natural number (except 1 ) or is simple, or it can be factorized in only one way.

When decomposing a number into prime factors, the signs of divisibility are used and the “column” notation is used. In this case, the divisor is located to the right of the vertical line, and the quotient is written under the dividend.

For example, task: factor a number into prime factors 330 . Solution:

Signs of divisibility into 2, 5, 3, 9, 10, 4, 25 and 11.

There are signs of divisibility into 6, 15, 45 etc., that is, into numbers whose product can be factorized 2, 3, 5, 9 And 10 .

Greatest common divisor

The largest natural number by which each of two given natural numbers is divisible is called greatest common divisor these numbers ( GCD). For example, GCD (10; 25) = 5; and GCD (18; 24) = 6; GCD (7; 21) = 1.

If the greatest common divisor of two natural numbers is equal to 1 , then these numbers are called mutually prime.

Algorithm for finding the greatest common divisor(NOD)

GCD is often used in problems. For example, 155 notebooks and 62 pens were divided equally between students in one class. How many students are there in this class?

Solution: Finding the number of students in this class comes down to finding the greatest common divisor of the numbers 155 and 62, since the notebooks and pens were divided equally. 155 = 5 31; 62 = 2 31. GCD (155; 62) = 31.

Answer: 31 students in the class.

Least common multiple

Multiples of a natural number A is a natural number that is divisible by A without a trace. For example, number 8 has multiples: 8, 16, 24, 32 , ... Any natural number has infinitely many multiples.

Least common multiple(LCM) is the smallest natural number that is a multiple of these numbers.

Algorithm for finding the least common multiple ( NOC):

LCM is also often used in problems. For example, two cyclists simultaneously started along a cycle track in the same direction. One makes a circle in 1 minute, and the other in 45 seconds. In what minimum number of minutes after the start of the movement will they meet at the start?

Solution: The number of minutes after which they will meet again at the start must be divided by 1 min, as well as on 45 s. In 1 min = 60 s. That is, it is necessary to find the LCM (45; 60). 45 = 32 5; 60 = 22 3 5. LCM (45; 60) = 22 32 5 = 4 9 5 = 180. The result is that the cyclists will meet at the start in 180 s = 3 min.

Answer: 3 min.

Division with remainder

If a natural number A is not divisible by a natural number b, then you can do division with remainder. In this case, the resulting quotient is called incomplete. The equality is fair:

a = b n + r,

Where A- divisible, b- divider, n- incomplete quotient, r- remainder. For example, let the dividend be equal 243 , divider - 4 , Then 243: 4 = 60 (remainder 3). That is, a = 243, b = 4, n = 60, r = 3, then 243 = 60 4 + 3 .

Numbers that are divisible by 2 without remainder, are called even: a = 2n, n ∈ N.

The remaining numbers are called odd: b = 2n + 1, n ∈ N.

This is a summary of the topic “Natural numbers. Signs of divisibility". To continue, select next steps:

• Go to next summary: