How to find nodes of numbers examples. What is a node. Finding the LCM by Factoring Numbers into Prime Factors

Lancinova Aisa

Download:

Preview:

To use the preview of presentations, create a Google account (account) and sign in: https://accounts.google.com

Slides captions:

Tasks for GCD and LCM of numbers The work of a 6th grade student of the MKOU "Kamyshovskaya OOSh" Lantsinova Aisa Supervisor Goryaeva Zoya Erdnigoryaevna, teacher of mathematics p. Kamyshovo, 2013

An example of finding the GCD of the numbers 50, 75 and 325. 1) Let's decompose the numbers 50, 75 and 325 into prime factors. 50= 2 ∙ 5 ∙ 5 75= 3 ∙ 5 ∙ 5 325= 5 ∙ 5 ∙ 13 50= 2 ∙ 5 ∙ 5 75= 3 ∙ 5 ∙ 5 325= 5 ∙ 5 ∙13 divide without a remainder the numbers a and b are called the greatest common divisor of these numbers.

An example of finding the LCM of the numbers 72, 99 and 117. 1) Let us factorize the numbers 72, 99 and 117. Write out the factors included in the expansion of one of the numbers 2 ∙ 2 ∙ 2 ∙ 3 ​​∙ 3 and add to them the missing factors of the remaining numbers. 2 ∙ 2 ∙ 2 ∙ 3 ​​∙ 3 ∙ 11 ∙ 13 3) Find the product of the resulting factors. 2 ∙ 2 ∙ 2 ∙ 3 ​​∙ 3 ∙ 11 ∙ 13= 10296 Answer: LCM (72, 99 and 117) = 10296 The least common multiple of natural numbers a and b is the smallest natural number that is a multiple of a and b.

A sheet of cardboard has the shape of a rectangle, the length of which is 48 cm and the width is 40 cm. This sheet must be cut without waste into equal squares. What are the largest squares that can be obtained from this sheet and how many? Solution: 1) S = a ∙ b is the area of ​​the rectangle. S \u003d 48 ∙ 40 \u003d 1960 cm². is the area of ​​the cardboard. 2) a - the side of the square 48: a - the number of squares that can be laid along the length of the cardboard. 40: a - the number of squares that can be laid across the width of the cardboard. 3) GCD (40 and 48) \u003d 8 (cm) - the side of the square. 4) S \u003d a² - the area of ​​\u200b\u200bone square. S \u003d 8² \u003d 64 (cm².) - the area of ​​\u200b\u200bone square. 5) 1960: 64 = 30 (number of squares). Answer: 30 squares with a side of 8 cm each. Tasks for GCD

The fireplace in the room must be laid out with finishing tiles in the shape of a square. How many tiles are needed for a 195 ͯ 156 cm fireplace and what are the largest tile sizes? Solution: 1) S = 196 ͯ 156 = 30420 (cm ²) - S of the fireplace surface. 2) GCD (195 and 156) = 39 (cm) - side of the tile. 3) S = a² = 39² = 1521 (cm²) - area of ​​1 tile. 4) 30420: = 20 (pieces). Answer: 20 tiles measuring 39 ͯ 39 (cm). Tasks for GCD

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

Out of 210 burgundy, 126 white, 294 red roses, bouquets were collected, and in each bouquet the number of roses of the same color is equal. What is the largest number of bouquets made from these roses and how many roses of each color are in one bouquet? Solution: 1) GCD (210, 126 and 294) = 42 (bouquets). 2) 210: 42 = 5 (burgundy roses). 3) 126: 42 = 3 (white roses). 4) 294: 42 = 7 (red roses). Answer: 42 bouquets: 5 burgundy, 3 white, 7 red roses in each bouquet. Tasks for GCD

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

Three tourist boat trips start in the port city, the first of which lasts 15 days, the second - 20 and the third - 12 days. Returning to the port, the ships on the same day again go on a voyage. Motor ships left the port on all three routes today. In how many days will they sail together for the first time? How many trips will each ship make? Solution: 1) NOC (15.20 and 12) = 60 (days) - meeting time. 2) 60: 15 = 4 (voyages) - 1 ship. 3) 60: 20 = 3 (voyages) - 2 motor ship. 4) 60: 12 = 5 (voyages) - 3 motor ship. Answer: 60 days, 4 flights, 3 flights, 5 flights. Tasks for the NOC

Masha bought eggs for the Bear in the store. On the way to the forest, she realized that the number of eggs is divisible by 2,3,5,10 and 15. How many eggs did Masha buy? Solution: LCM (2;3;5;10;15) = 30 (eggs) Answer: Masha bought 30 eggs. Tasks for the NOC

It is required to make a box with a square bottom for stacking boxes measuring 16 ͯ 20 cm. What should be the shortest side of the square bottom to fit the boxes tightly into the box? Solution: 1) NOC (16 and 20) = 80 (boxes). 2) S = a ∙ b is the area of ​​1 box. S \u003d 16 ∙ 20 \u003d 320 (cm ²) - the area of ​​​​the bottom of 1 box. 3) 320 ∙ 80 = 25600 (cm ²) - square bottom area. 4) S \u003d a² \u003d a ∙ a 25600 \u003d 160 ∙ 160 - the dimensions of the box. Answer: 160 cm is the side of the square bottom. Tasks for the NOC

Along the road from point K there are power poles every 45 m. It was decided to replace these poles with others, placing them at a distance of 60 m from each other. How many poles were there and how many will they stand? Solution: 1) NOK (45 and 60) = 180. 2) 180: 45 = 4 - there were pillars. 3) 180: 60 = 3 - there were pillars. Answer: 4 pillars, 3 pillars. Tasks for the NOC

How many soldiers are marching on the parade ground if they march in formation of 12 people in a line and change into a column of 18 people in a line? Solution: 1) NOC (12 and 18) = 36 (people) - marching. Answer: 36 people. Tasks for the NOC

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 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:

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 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:

1. Decompose numbers into prime factors
2. 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

1. Any common multiple of $a$ and $b$ is divisible by K$(a;b)$
2. 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)$

Euclid's algorithm is an algorithm for finding the greatest common divisor (gcd) of a pair of integers.

Greatest Common Divisor (GCD) is a number that divides two numbers without a remainder and is itself divisible without a remainder by any other divisor of the given two numbers. Simply put, this is the largest number by which the two numbers for which the gcd is sought can be divided without a remainder.

Algorithm for finding GCD by division

1. Divide the larger number by the smaller one.
2. If it is divided without a remainder, then the smaller number is the GCD (you should exit the loop).
3. If there is a remainder, then more replaced by the remainder of the division.
4. Let's move on to point 1.

Example:
Find GCD for 30 and 18.
30 / 18 = 1 (remainder 12)
18 / 12 = 1 (remainder 6)
12 / 6 = 2 (remainder 0)
End: GCD is the divisor of 6.
gcd(30, 18) = 6

a = 50 b = 130 while a != 0 and b != 0 : if a > b: a = a % b else : b = b % a print (a + b)

In the loop, the remainder of the division is written to the variable a or b. The loop ends when at least one of the variables is zero. This means that the other contains GCD. However, we don't know which one. Therefore, for GCD we find the sum of these variables. Since one of the variables is zero, it has no effect on the result.

Algorithm for finding GCD by subtraction

1. Subtract the smaller from the larger number.
2. If it turns out 0, then it means that the numbers are equal to each other and are GCD (you should exit the loop).
3. If the result of the subtraction is not equal to 0, then the larger number is replaced by the result of the subtraction.
4. Let's move on to point 1.

Example:
Find GCD for 30 and 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
End: GCD is the minuend or the subtrahend.
gcd(30, 18) = 6

a = 50 b = 130 while a != b: if a > b: a = a - b else : b = b - a print (a)

To learn how to find the greatest common divisor of two or more numbers, you need to understand what natural, prime and complex numbers are.

A natural number is any number that is used to count integers.

If a natural number can only be divided by itself and one, then it is called prime.

All natural numbers can be divided by themselves and one, but the only even prime number is 2, all others can be divided by two. Therefore, only simple odd numbers.

Too many prime numbers complete list they don't exist. To find the GCD, it is convenient to use special tables with such numbers.

Most natural numbers can be divided not only by one, themselves, but also by other numbers. So, for example, the number 15 can be divided by 3 and 5. All of them are called divisors of the number 15.

Thus, the divisor of any A is the number by which it can be divided without a remainder. If a number has more than two natural divisors, it is called composite.

The number 30 has such divisors as 1, 3, 5, 6, 15, 30.

You can see that 15 and 30 have the same divisors 1, 3, 5, 15. The greatest common divisor of these two numbers is 15.

Thus, the common divisor of the numbers A and B is the number by which you can divide them completely. The maximum can be considered the maximum total number into which they can be divided.

To solve problems, the following abbreviated inscription is used:

GCD (A; B).

For example, GCD (15; 30) = 30.

To write down all divisors of a natural number, the notation is used:

D(15) = (1, 3, 5, 15)

gcd (9; 15) = 1

In this example, natural numbers have only one common divisor. They are called coprime, respectively, the unit is their greatest common divisor.

How to find the greatest common divisor of numbers

To find the GCD of several numbers, you need:

Find all divisors of each natural number separately, that is, decompose them into factors (prime numbers);

Select all the same factors for given numbers;

Multiply them together.

For example, to calculate the greatest common divisor of the numbers 30 and 56, you would write the following:

In order not to get confused with , it is convenient to write the multipliers using vertical columns. On the left side of the line, you need to place the dividend, and on the right - the divisor. Under the dividend, you should indicate the resulting quotient.

So, in the right column will be all the factors needed for the solution.

Identical divisors (factors found) can be underlined for convenience. They should be rewritten and multiplied and the greatest common divisor should be written down.

GCD (30; 56) = 2 * 5 = 10

It's really that simple to find the greatest common divisor of numbers. With a little practice, you can do it almost automatically.

Let's continue the discussion about the least common multiple that we started in the LCM - Least Common Multiple, Definition, Examples section. In this topic, we will look at ways to find the LCM for three numbers or more, we will analyze the question of how to find the LCM of a negative number.

Calculation of the least common multiple (LCM) through gcd

We have already established the relationship between the least common multiple and the greatest common divisor. Now let's learn how to define the LCM through the GCD. First, let's figure out how to do this for positive numbers.

Definition 1

You can find the least common multiple through the greatest common divisor using the formula LCM (a, b) \u003d a b: GCD (a, b) .

Example 1

It is necessary to find the LCM of the numbers 126 and 70.

Solution

Let's take a = 126 , b = 70 . Substitute the values ​​in the formula for calculating the least common multiple through the greatest common divisor LCM (a, b) = a · b: GCD (a, b) .

Finds the GCD of the numbers 70 and 126. For this we need the Euclid algorithm: 126 = 70 1 + 56 , 70 = 56 1 + 14 , 56 = 14 4 , hence gcd (126 , 70) = 14 .

Let's calculate the LCM: LCM (126, 70) = 126 70: GCD (126, 70) = 126 70: 14 = 630.

Answer: LCM (126, 70) = 630.

Example 2

Find the nok of the numbers 68 and 34.

Solution

GCD in this case is easy to find, since 68 is divisible by 34. Calculate the least common multiple using the formula: LCM (68, 34) = 68 34: GCD (68, 34) = 68 34: 34 = 68.

Answer: LCM(68, 34) = 68.

In this example, we used the rule for finding the least common multiple of positive integers a and b: if the first number is divisible by the second, then the LCM of these numbers will be equal to the first number.

Finding the LCM by Factoring Numbers into Prime Factors

Now let's look at a way to find the LCM, which is based on the decomposition of numbers into prime factors.

Definition 2

To find the least common multiple, we need to perform a number of simple steps:

• we make up the product of all prime factors of numbers for which we need to find the LCM;
• we exclude all prime factors from their obtained products;
• the product obtained after eliminating the common prime factors will be equal to the LCM of the given numbers.

This way of finding the least common multiple is based on the equality LCM (a , b) = a b: GCD (a , b) . If you look at the formula, it will become clear: the product of the numbers a and b is equal to the product of all factors that are involved in the expansion of these two numbers. In this case, the GCD of two numbers is equal to the product of all prime factors that are simultaneously present in the factorizations of these two numbers.

Example 3

We have two numbers 75 and 210 . We can factor them out like this: 75 = 3 5 5 and 210 = 2 3 5 7. If you make the product of all the factors of the two original numbers, you get: 2 3 3 5 5 5 7.

If we exclude the factors common to both numbers 3 and 5, we get a product of the following form: 2 3 5 5 7 = 1050. This product will be our LCM for the numbers 75 and 210.

Example 4

Find the LCM of numbers 441 and 700 , decomposing both numbers into prime factors.

Solution

Let's find all the prime factors of the numbers given in the condition:

441 147 49 7 1 3 3 7 7

700 350 175 35 7 1 2 2 5 5 7

We get two chains of numbers: 441 = 3 3 7 7 and 700 = 2 2 5 5 7 .

The product of all the factors that participated in the expansion of these numbers will look like: 2 2 3 3 5 5 7 7 7. Let's find the common factors. This number is 7 . We exclude it from the general product: 2 2 3 3 5 5 7 7. It turns out that NOC (441 , 700) = 2 2 3 3 5 5 7 7 = 44 100.

Answer: LCM (441 , 700) = 44 100 .

Let us give one more formulation of the method for finding the LCM by decomposing numbers into prime factors.

Definition 3

Previously, we excluded from the total number of factors common to both numbers. Now we will do it differently:

• Let's decompose both numbers into prime factors:
• add to the product of the prime factors of the first number the missing factors of the second number;
• we get the product, which will be the desired LCM of two numbers.

Example 5

Let's go back to the numbers 75 and 210 , for which we already looked for the LCM in one of the previous examples. Let's break them down into simple factors: 75 = 3 5 5 and 210 = 2 3 5 7. To the product of factors 3 , 5 and 5 number 75 add the missing factors 2 and 7 numbers 210 . We get: 2 3 5 5 7 . This is the LCM of the numbers 75 and 210.

Example 6

It is necessary to calculate the LCM of the numbers 84 and 648.

Solution

Let's decompose the numbers from the condition into prime factors: 84 = 2 2 3 7 and 648 = 2 2 2 3 3 3 3. Add to the product of the factors 2 , 2 , 3 and 7 numbers 84 missing factors 2 , 3 , 3 and
3 numbers 648 . We get the product 2 2 2 3 3 3 3 7 = 4536 . This is the least common multiple of 84 and 648.

Answer: LCM (84, 648) = 4536.

Finding the LCM of three or more numbers

Regardless of how many numbers we are dealing with, the algorithm of our actions will always be the same: we will consistently find the LCM of two numbers. There is a theorem for this case.

Theorem 1

Suppose we have integers a 1 , a 2 , … , a k. NOC m k of these numbers is found in sequential calculation m 2 = LCM (a 1 , a 2) , m 3 = LCM (m 2 , a 3) , … , m k = LCM (m k − 1 , a k) .

Now let's look at how the theorem can be applied to specific problems.

Example 7

You need to calculate the least common multiple of the four numbers 140 , 9 , 54 and 250 .

Solution

Let's introduce the notation: a 1 \u003d 140, a 2 \u003d 9, a 3 \u003d 54, a 4 \u003d 250.

Let's start by calculating m 2 = LCM (a 1 , a 2) = LCM (140 , 9) . Let's use the Euclidean algorithm to calculate the GCD of the numbers 140 and 9: 140 = 9 15 + 5 , 9 = 5 1 + 4 , 5 = 4 1 + 1 , 4 = 1 4 . We get: GCD(140, 9) = 1, LCM(140, 9) = 140 9: GCD(140, 9) = 140 9: 1 = 1260. Therefore, m 2 = 1 260 .

Now let's calculate according to the same algorithm m 3 = LCM (m 2 , a 3) = LCM (1 260 , 54) . In the course of calculations, we get m 3 = 3 780.

It remains for us to calculate m 4 \u003d LCM (m 3, a 4) \u003d LCM (3 780, 250) . We act according to the same algorithm. We get m 4 \u003d 94 500.

The LCM of the four numbers from the example condition is 94500 .

Answer: LCM (140, 9, 54, 250) = 94,500.

As you can see, the calculations are simple, but quite laborious. To save time, you can go the other way.

Definition 4

We offer you the following algorithm of actions:

• decompose all numbers into prime factors;
• to the product of the factors of the first number, add the missing factors from the product of the second number;
• add the missing factors of the third number to the product obtained at the previous stage, etc.;
• the resulting product will be the least common multiple of all numbers from the condition.

Example 8

It is necessary to find the LCM of five numbers 84 , 6 , 48 , 7 , 143 .

Solution

Let's decompose all five numbers into prime factors: 84 = 2 2 3 7 , 6 = 2 3 , 48 = 2 2 2 2 3 , 7 , 143 = 11 13 . Prime numbers, which is the number 7, cannot be factored into prime factors. Such numbers coincide with their decomposition into prime factors.

Now let's take the product of the prime factors 2, 2, 3 and 7 of the number 84 and add to them the missing factors of the second number. We have decomposed the number 6 into 2 and 3. These factors are already in the product of the first number. Therefore, we omit them.

We continue to add the missing multipliers. We turn to the number 48, from the product of prime factors of which we take 2 and 2. Then we add a simple factor of 7 from the fourth number and factors of 11 and 13 of the fifth. We get: 2 2 2 2 3 7 11 13 = 48,048. This is the least common multiple of the five original numbers.

Answer: LCM (84, 6, 48, 7, 143) = 48,048.

Finding the Least Common Multiple of Negative Numbers

To find the least common multiple negative numbers, these numbers must first be replaced by numbers with the opposite sign, and then the calculations should be carried out according to the above algorithms.

Example 9

LCM(54, −34) = LCM(54, 34) and LCM(−622,−46, −54,−888) = LCM(622, 46, 54, 888) .

Such actions are permissible due to the fact that if it is accepted that a and − a- opposite numbers
then the set of multiples a coincides with the set of multiples of a number − a.

Example 10

It is necessary to calculate the LCM of negative numbers − 145 and − 45 .

Solution

Let's change the numbers − 145 and − 45 to their opposite numbers 145 and 45 . Now, using the algorithm, we calculate the LCM (145 , 45) = 145 45: GCD (145 , 45) = 145 45: 5 = 1 305 , having previously determined the GCD using the Euclid algorithm.

We get that the LCM of numbers − 145 and − 45 equals 1 305 .

Answer: LCM (− 145 , − 45) = 1 305 .

If you notice a mistake in the text, please highlight it and press Ctrl+Enter