Node of three numbers examples. Finding the least common multiple, methods, examples of finding the LCM

Finding the greatest common divisor of three or 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 equal to the number dk, which is found by 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 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 divisor 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 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 =GCD(78, 294)=6.

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

It remains to calculate d 4 =GCD(d 3, a 4)=GCD(6, 36). Because 36 divided by 6 , That d 4 =GCD(6, 36)=6.

Thus, the greatest common divisor of the four given numbers is equal to 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 break down the numbers 78 , 294 , 570 And 36 by 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 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 moduli of these numbers. This is due to the fact that opposite numbers a And −a have the same divisors, as 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). The Euclidean 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 is −231 And −140 equals 7 .

Answer:

GCD(−231, −140)=7.

Example.

Determine the gcd of three numbers −585 , 81 And −189 .

Solution.

When 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 have 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 above)

36. Multiple roots, criterion for multiplicity of roots.

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 a bunch of decisions. Let's find them all. First of all, let's factor this number into simple 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 a bunch of 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 a notation 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 take a 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 more briefly, namely:

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

Here the special icon “∩” (“bag with the hole down”) indicates that from the two sets written on opposite sides of it, only common elements must be selected. 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 Union, 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. Here are all the possible shortcuts (except for the uninteresting shortening by one):

Obviously, it is most practical to reduce the fraction by a number that is as large as possible. 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 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 GCD is 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 denominators are factored into prime factors:

105 = 3 ∙ 5 ∙ 7 ;

140 = 2 ∙ 2 ∙ 5 ∙ 7 .

From this decomposition it immediately follows that, in order to bring fractions to a 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 (“product” unstressed 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:

Second number: b=

Thousand separator Without space separator "´

Result:

Greatest common divisor gcd( a,b)=6

Least common multiple of LCM( a,b)=468

The largest natural number that can be divided without a remainder by numbers a and b is called greatest common divisor(GCD) of these numbers. Denoted by gcd(a,b), (a,b), gcd(a,b) or hcf(a,b).

Least common multiple The LCM of two integers a and b is the smallest natural number that is divisible by a and b without a remainder. Denoted LCM(a,b), or lcm(a,b).

The integers a and b are called mutually prime, if they have no common divisors other than +1 and −1.

Greatest common divisor

Let two positive numbers be given a 1 and a 2 1). It is required to find the common divisor of these numbers, i.e. find such a number λ , which divides numbers a 1 and a 2 at the same time. Let's describe the algorithm.

1) In this article, the word number will be understood as an integer.

Let a 1 ≥ a 2 and let

Where m 1 , a 3 are some integers, a 3 <a 2 (remainder of division a 1 per a 2 should be less a 2).

Let's pretend that λ divides a 1 and a 2 then λ divides m 1 a 2 and λ divides a 1 −m 1 a 2 =a 3 (Statement 2 of the article “Divisibility of numbers. Divisibility test”). It follows that every common divisor a 1 and a 2 is the common divisor a 2 and a 3. The reverse is also true if λ common divisor a 2 and a 3 then m 1 a 2 and a 1 =m 1 a 2 +a 3 is also divisible by λ . Therefore the common divisor a 2 and a 3 is also a common divisor a 1 and a 2. Because a 3 <a 2 ≤a 1, then we can say that the solution to the problem of finding the common divisor of numbers a 1 and a 2 reduced to the simpler problem of finding the common divisor of numbers a 2 and a 3 .

If a 3 ≠0, then we can divide a 2 on a 3. Then

,

Where m 1 and a 4 are some integers, ( a 4 remainder from division a 2 on a 3 (a 4 <a 3)). By similar reasoning we come to the conclusion that common divisors of numbers a 3 and a 4 coincides with common divisors of numbers a 2 and a 3, and also with common divisors a 1 and a 2. Because a 1 , a 2 , a 3 , a 4, ... are numbers that are constantly decreasing, and since there is a finite number of integers between a 2 and 0, then at some step n, remainder of the division a n on a n+1 will be equal to zero ( a n+2 =0).

.

Every common divisor λ numbers a 1 and a 2 is also a divisor of numbers a 2 and a 3 , a 3 and a 4 , .... a n and a n+1 . The converse is also true, common divisors of numbers a n and a n+1 are also divisors of numbers a n−1 and a n , .... , a 2 and a 3 , a 1 and a 2. But the common divisor of numbers a n and a n+1 is a number a n+1 , because a n and a n+1 are divisible by a n+1 (remember that a n+2 =0). Hence a n+1 is also a divisor of numbers a 1 and a 2 .

Note that the number a n+1 is the largest divisor of numbers a n and a n+1 , since the greatest divisor a n+1 is itself a n+1 . If a n+1 can be represented as a product of integers, then these numbers are also common divisors of numbers a 1 and a 2. Number a n+1 is called greatest common divisor numbers a 1 and a 2 .

Numbers a 1 and a 2 can be either positive or negative numbers. If one of the numbers is equal to zero, then the greatest common divisor of these numbers will be equal to the absolute value of the other number. The greatest common divisor of zero numbers is undefined.

The above algorithm is called Euclidean algorithm to find the greatest common divisor of two integers.

An example of finding the greatest common divisor of two numbers

Find the greatest common divisor of two numbers 630 and 434.

• Step 1. Divide the number 630 by 434. The remainder is 196.
• Step 2. Divide the number 434 by 196. The remainder is 42.
• Step 3. Divide the number 196 by 42. The remainder is 28.
• Step 4. Divide the number 42 by 28. The remainder is 14.
• Step 5. Divide the number 28 by 14. The remainder is 0.

In step 5, the remainder of the division is 0. Therefore, the greatest common divisor of the numbers 630 and 434 is 14. Note that the numbers 2 and 7 are also divisors of the numbers 630 and 434.

Coprime numbers

Definition 1. Let the greatest common divisor of the numbers a 1 and a 2 is equal to one. Then these numbers are called coprime numbers, having no common divisor.

Theorem 1. If a 1 and a 2 coprime numbers, and λ some number, then any common divisor of numbers λa 1 and a 2 is also a common divisor of numbers λ And a 2 .

Proof. Consider the Euclidean algorithm for finding the greatest common divisor of numbers a 1 and a 2 (see above).

.

From the conditions of the theorem it follows that the greatest common divisor of the numbers a 1 and a 2 and therefore a n and a n+1 is 1. That is a n+1 =1.

Let's multiply all these equalities by λ , Then

.

Let the common divisor a 1 λ And a 2 yes δ . Then δ is included as a multiplier in a 1 λ , m 1 a 2 λ and in a 1 λ -m 1 a 2 λ =a 3 λ (see "Divisibility of numbers", Statement 2). Further δ is included as a multiplier in a 2 λ And m 2 a 3 λ , and, therefore, is included as a factor in a 2 λ -m 2 a 3 λ =a 4 λ .

Reasoning this way, we are convinced that δ is included as a multiplier in a n−1 λ And m n−1 a n λ , and therefore in a n−1 λ −m n−1 a n λ =a n+1 λ . Because a n+1 =1, then δ is included as a multiplier in λ . Therefore the number δ is the common divisor of numbers λ And a 2 .

Let us consider special cases of Theorem 1.

Consequence 1. Let a And c Prime numbers are relatively b. Then their product ac is a prime number with respect to b.

Really. From Theorem 1 ac And b have the same common divisors as c And b. But the numbers c And b relatively simple, i.e. have a single common divisor 1. Then ac And b also have a single common divisor 1. Therefore ac And b mutually simple.

Consequence 2. Let a And b coprime numbers and let b divides ak. Then b divides and k.

Really. From the approval condition ak And b have a common divisor b. By virtue of Theorem 1, b must be a common divisor b And k. Hence b divides k.

Corollary 1 can be generalized.

Consequence 3. 1. Let the numbers a 1 , a 2 , a 3 , ..., a m are prime relative to the number b. Then a 1 a 2 , a 1 a 2 · a 3 , ..., a 1 a 2 a 3 ··· a m, the product of these numbers is prime relative to the number b.

2. Let us have two rows of numbers

such that every number in the first series is prime in the ratio of every number in the second series. Then the product

You need to find numbers that are divisible by each of these numbers.

If a number is divisible by a 1, then it has the form sa 1 where s some number. If q is the greatest common divisor of numbers a 1 and a 2, then

Where s 1 is some integer. Then

is least common multiples of numbers a 1 and a 2 .

a 1 and a 2 are relatively prime, then the least common multiple of the numbers a 1 and a 2:

We need to find the least common multiple of these numbers.

From the above it follows that any multiple of numbers a 1 , a 2 , a 3 must be a multiple of numbers ε And a 3 and back. Let the least common multiple of the numbers ε And a 3 yes ε 1 . Next, multiples of numbers a 1 , a 2 , a 3 , a 4 must be a multiple of numbers ε 1 and a 4 . Let the least common multiple of the numbers ε 1 and a 4 yes ε 2. Thus, we found out that all multiples of numbers a 1 , a 2 , a 3 ,...,a m coincide with multiples of a certain number ε n, which is called the least common multiple of the given numbers.

In the special case when the numbers a 1 , a 2 , a 3 ,...,a m are relatively prime, then the least common multiple of the numbers a 1 , a 2, as shown above, has the form (3). Next, since a 3 prime in relation to numbers a 1 , a 2 then a 3 prime number a 1 · a 2 (Corollary 1). Means the least common multiple of the numbers a 1 ,a 2 ,a 3 is a number a 1 · a 2 · a 3. Reasoning in a similar way, we arrive at the following statements.

Statement 1. Least common multiple of coprime numbers a 1 , a 2 , a 3 ,...,a m is equal to their product a 1 · a 2 · a 3 ··· a m.

Statement 2. Any number that is divisible by each of the coprime numbers a 1 , a 2 , a 3 ,...,a m is also divisible by their product a 1 · a 2 · a 3 ··· a m.

Lancinova Aisa

Download:

Preview:

To use presentation previews, create a Google account and log in to it: https://accounts.google.com

Slide captions:

Problems on GCD and LCM of numbers Work of a 6th grade student of the MCOU "Kamyshovskaya secondary school" Lantsinova Aisa Supervisor Zoya Erdnigoryaevna Goryaeva, mathematics teacher p. Kamyshevo, 2013

An example of finding the gcd of the numbers 50, 75 and 325. 1) Let's factor the numbers 50, 75 and 325 into prime factors. 50= 2 ∙ 5 ∙ 5 75= 3 ∙ 5 ∙ 5 325= 5 ∙ 5 ∙ 13 2) 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 others. 50= 2 ∙ 5 ∙ 5 75= 3 ∙ 5 ∙ 5 325= 5 ∙ 5 ∙13 3) Find the product of the remaining factors 5 ∙ 5 = 25 Answer: GCD (50, 75 and 325) = 25 The largest natural number by which When numbers a and b are divided without remainder, the greatest common divisor of these numbers is called the greatest common divisor of these numbers.

An example of finding the LCM of the numbers 72, 99 and 117. 1) Let's factor the numbers 72, 99 and 117 into prime factors. 72 = 2 ∙ 2 ∙ 2 ∙ 3 ​​∙ 3 99 = 3 ∙ 3 ∙ 11 117 = 3 ∙ 3 ∙13 2) Write down 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 into equal squares without waste. What are the largest squares that can be obtained from this worksheet and how many? Solution: 1) S = a ∙ b – area of ​​the rectangle. S= 48 ∙ 40 = 1960 cm². – area of ​​cardboard. 2) a – 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) = 8 (cm) – side of the square. 4) S = a² – area of ​​one square. S = 8² = 64 (cm²) – area of ​​one square. 5) 1960: 64 = 30 (number of squares). Answer: 30 squares with a side of 8 cm each. GCD problems

The fireplace in the room must be tiled in the shape of a square. How many tiles will be needed for a fireplace measuring 195 ͯ 156 cm 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). GCD problems

A garden plot measuring 54 ͯ 48 m around the perimeter must be fenced; to do this, concrete pillars must be placed at regular intervals. How many poles need to be brought for the site, and at what maximum distance from each other will the poles be placed? Solution: 1) P = 2(a + b) – perimeter of the site. P = 2(54 + 48) = 204 m. 2) GCD (54 and 48) = 6 (m) – the distance between the pillars. 3) 204: 6 = 34 (pillars). Answer: 34 pillars, at a distance of 6 m. GCD problems

Bouquets were collected from 210 burgundy, 126 white, and 294 red roses, with each bouquet containing an equal number of roses of the same color. 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. GCD problems

Tanya and Masha bought the same number of postal kits. Tanya paid 90 rubles, and Masha paid 5 rubles. more. How much does one set cost? How many sets did each person buy? Solution: 1) 90 + 5 = 95 (rub.) Masha paid. 2) GCD (90 and 95) = 5 (rub.) – price of 1 set. 3) 980: 5 = 18 (sets) – bought by Tanya. 4) 95: 5 = 19 (sets) – bought by Masha. Answer: 5 rubles, 18 sets, 19 sets. GCD problems

Three tourist boat trips begin in the port city, the first of which lasts 15 days, the second – 20 and the third – 12 days. Having returned to the port, the ships set off again on the same day. Today, ships left the port on all three routes. In how many days will they set sail together again 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 ships. 4) 60: 12 = 5 (flights) – 3 ships. Answer: 60 days, 4 flights, 3 flights, 5 flights. NOC tasks

Masha bought eggs for the Bear at 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: LOC (2;3;5;10;15) = 30 (eggs) Answer: Masha bought 30 eggs. NOC tasks

It is required to make a box with a square bottom to accommodate boxes measuring 16 ͯ 20 cm. What is the shortest length of the side of the square bottom to fit the boxes tightly into the box? Solution: 1) LCM (16 and 20) = 80 (boxes). 2) S = a ∙ b – area of ​​1 box. S = 16 ∙ 20 = 320 (cm²) – bottom area of ​​1 box. 3) 320 ∙ 80 = 25600 (cm²) – area of ​​the square bottom. 4) S = a² = a ∙ a 25600 = 160 ∙ 160 – dimensions of the box. Answer: 160 cm is the side of the square bottom. NOC tasks

Along the road from point K there are power poles every 45 m. They decided to replace these poles with others, placing them at a distance of 60 m from each other. How many pillars were there and how many will there be? Solution: 1) LCM (45 and 60) = 180. 2) 180: 45 = 4 – there were pillars. 3) 180: 60 = 3 – became pillars. Answer: 4 pillars, 3 pillars. NOC tasks

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. NOC tasks

Greatest common divisor

Definition 2

If a natural number a is divisible by a natural number $b$, then $b$ is called a divisor of $a$, and $a$ is called a multiple of $b$.

Let $a$ and $b$ be natural numbers. The number $c$ is called the common divisor of 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 a largest one, which is called the greatest common divisor of the numbers $a$ and $b$ and is denoted by the following notation:

$GCD\(a;b)\ or \D\(a;b)$

To find the greatest common divisor of two numbers you need:

1. 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 the monomials $63$ and $81$.

We will find according to the presented algorithm. For this:

Let's factor the 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 a set of divisors of numbers.

Example 3

Find the gcd of the numbers $48$ and $60$.

Solution:

Let's find the set of divisors of the number $48$: $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\right\)$

Now let's find the set of divisors of the number $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$. This means that the greatest common divisor of the numbers $48$ and $60$ is $12$.

Definition of NPL

Definition 3

Common multiples 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 numbers without a remainder. For example, for the numbers $25$ and $50$, the common multiples will be the numbers $50,100,150,200$, etc.

The smallest common multiple will be called the least common multiple and will be denoted LCM$(a;b)$ or K$(a;b).$

To find the LCM of two numbers, you need to:

1. Factor numbers into prime factors
2. Write down the factors that are part of the first number and add to them the factors that are part of the second and are not part of the first

Example 4

Find the LCM of the numbers $99$ and $77$.

We will find according to the presented algorithm. For this

Factor numbers into prime factors

$99=3\cdot 3\cdot 11$

Write down the factors included in the first

add to them multipliers that are part of the second and not part of the first

Find the product of the numbers found in step 2. The resulting number will be the desired least common multiple

$NOK=3\cdot 3\cdot 11\cdot 7=693$

Compiling lists of divisors of numbers is often a very labor-intensive task. There is a way to find GCD called the Euclidean algorithm.

Statements on which the Euclidean 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 reduce 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

1. Any common multiple of $a$ and $b$ is divisible by K$(a;b)$
2. If $a\vdots b$ , then К$(a;b)=a$

If K$(a;b)=k$ and $m$ is a 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 the common multiple of $a$ and $b$

For any natural numbers $a$ and $b$ the equality holds

$D(a;b)\cdot К(a;b)=ab$

Any common divisor of the numbers $a$ and $b$ is a divisor of the number $D(a;b)$