Divisibility criteria for natural numbers.
Numbers divisible by 2 without a remainder are calledeven .
Numbers that are not evenly divisible by 2 are calledodd .
Test for divisibility by 2
If a natural number ends with an even digit, then this number is divisible by 2 without a remainder, and if a number ends with an odd digit, then this number is not evenly divisible by 2.
For example, the numbers 60 , 30 8 , 8 4 are divisible by 2 without remainder, and the numbers are 51 , 8 5 , 16 7 are not divisible by 2 without a remainder.
Test for divisibility by 3
If the sum of the digits of a number is divisible by 3, then the number is divisible by 3; If the sum of the digits of a number is not divisible by 3, then the number is not divisible by 3.
For example, let’s find out whether the number 2772825 is divisible by 3. To do this, let’s calculate the sum of the digits of this number: 2+7+7+2+8+2+5 = 33 - divisible by 3. This means the number 2772825 is divisible by 3.
Divisibility test by 5
If the record of a natural number ends with the digit 0 or 5, then this number is divisible by 5 without a remainder. If the record of a number ends with another digit, then the number is not divisible by 5 without a remainder.
For example, the numbers 15 , 3 0 , 176 5 , 47530 0 are divisible by 5 without remainder, and the numbers are 17 , 37 8 , 9 1 don't share.
Divisibility test by 9
If the sum of the digits of a number is divisible by 9, then the number is divisible by 9; If the sum of the digits of a number is not divisible by 9, then the number is not divisible by 9.
For example, let’s find out whether the number 5402070 is divisible by 9. To do this, let’s calculate the sum of the digits of this number: 5+4+0+2+0+7+0 = 16 - not divisible by 9. This means the number 5402070 is not divisible by 9.
Divisibility test by 10
If a natural number ends with the digit 0, then this number is divisible by 10 without a remainder. If a natural number ends with another digit, then it is not evenly divisible by 10.
For example, the numbers 40 , 17 0 , 1409 0 are divisible by 10 without remainder, and the numbers 17 , 9 3 , 1430 7 - don't share.
The rule for finding the greatest common divisor (GCD).
To find the greatest common divisor of several natural numbers, you need to:
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.
Example. Let's find GCD (48;36). Let's use the rule.
1. Let's factor the numbers 48 and 36 into prime factors.
48 = 2 · 2 · 2 · 2 · 3
36 = 2 · 2 · 3 · 3
2. From the factors included in the expansion of the number 48, we delete those that are not included in the expansion of the number 36.
48 = 2 · 2 · 2 · 2 · 3
The remaining factors are 2, 2 and 3.
3. Multiply the remaining factors and get 12. This number is the greatest common divisor of the numbers 48 and 36.
GCD (48;36) = 2· 2 · 3 = 12.
The rule for finding the least common multiple (LCM).
To find the least common multiple of several natural numbers, you need to:
1) factor them into prime factors;
2) write down 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.
Example. Let's find the LOC (75;60). Let's use the rule.
1. Let's factor the numbers 75 and 60 into prime factors.
75 = 3 · 5 · 5
60 = 2 · 2 · 3 · 3
2. Let’s write down the factors included in the expansion of the number 75: 3, 5, 5.
LCM(75;60) = 3 · 5 · 5 · …
3. Add to them the missing factors from the expansion of the number 60, i.e. 2, 2.
LCM(75;60) = 3 · 5 · 5 · 2 · 2
4. Find the product of the resulting factors
LCM(75;60) = 3 · 5 · 5 · 2 · 2 = 300.
The least common multiple of two numbers is directly related to the greatest common divisor of those numbers. This connection between GCD and NOC is determined by the following theorem.
Theorem.
The least common multiple of two positive integers a and b is equal to the product of a and b divided by the greatest common divisor of a and b, that is, LCM(a, b)=a b:GCD(a, b).
Proof.
Let M is some multiple of the numbers a and b. That is, M is divisible by a, and by the definition of divisibility, there is some integer k such that the equality M=a·k is true. But M is also divisible by b, then a·k is divisible by b.
Let's denote gcd(a, b) as d. Then we can write the equalities a=a 1 ·d and b=b 1 ·d, and a 1 =a:d and b 1 =b:d will be relatively prime numbers. Consequently, the condition obtained in the previous paragraph that a · k is divisible by b can be reformulated as follows: a 1 · d · k is divided by b 1 · d , and this, due to divisibility properties, is equivalent to the condition that a 1 · k is divisible by b 1 .
You also need to write down two important corollaries from the theorem considered.
The common multiples of two numbers are the same as the multiples of their least common multiple.
This is indeed the case, since any common multiple of M of the numbers a and b is determined by the equality M=LMK(a, b)·t for some integer value t.
The least common multiple of mutually prime positive numbers a and b is equal to their product.
The rationale for this fact is quite obvious. Since a and b are relatively prime, then gcd(a, b)=1, therefore, GCD(a, b)=a b: GCD(a, b)=a b:1=a b.
Least common multiple of three or more numbers
Finding the least common multiple of three or more numbers can be reduced to sequentially finding the LCM of two numbers. How this is done is indicated in the following theorem. a 1 , a 2 , …, a k coincide with the common multiples of the numbers m k-1 and a k , therefore, coincide with the common multiples of the number m k . And since the smallest positive multiple of the number m k is the number m k itself, then the smallest common multiple of the numbers a 1, a 2, ..., a k is m k.
Bibliography.
- Vilenkin N.Ya. and others. Mathematics. 6th grade: textbook for general education institutions.
- Vinogradov I.M. Fundamentals of number theory.
- Mikhelovich Sh.H. Number theory.
- Kulikov L.Ya. and others. Collection of problems in algebra and number theory: Textbook for students of physics and mathematics. specialties of pedagogical institutes.
Mathematical expressions and problems require a lot of additional knowledge. NOC is one of the main ones, especially often used in The topic is studied in high school, and it is not particularly difficult to understand material; a person familiar with powers and the multiplication table will not have difficulty identifying the necessary numbers and discovering the result.
Definition
A common multiple is a number that can be completely divided into two numbers at the same time (a and b). Most often, this number is obtained by multiplying the original numbers a and b. The number must be divisible by both numbers at once, without deviations.
NOC is the short name adopted for the designation, collected from the first letters.
Ways to get a number
The method of multiplying numbers is not always suitable for finding the LCM; it is much better suited for simple single-digit or two-digit numbers. It is customary to divide into factors; the larger the number, the more factors there will be.
Example #1
For the simplest example, schools usually use prime, single- or double-digit numbers. For example, you need to solve the following task, find the least common multiple of the numbers 7 and 3, the solution is quite simple, just multiply them. As a result, there is a number 21, there is simply no smaller number.
Example No. 2
The second version of the task is much more difficult. The numbers 300 and 1260 are given, finding the LOC is mandatory. To solve the problem, the following actions are assumed:
Decomposition of the first and second numbers into simple factors. 300 = 2 2 * 3 * 5 2 ; 1260 = 2 2 * 3 2 *5 *7. The first stage is completed.
The second stage involves working with already obtained data. Each of the numbers received must participate in calculating the final result. For each factor, the largest number of occurrences is taken from the original numbers. LCM is a general number, so the factors of the numbers must be repeated in it, every single one, even those that are present in one copy. Both initial numbers contain the numbers 2, 3 and 5, in different powers; 7 is present only in one case.
To calculate the final result, you need to take each number in the largest of the powers represented into the equation. All that remains is to multiply and get the answer; if filled out correctly, the task fits into two steps without explanation:
1) 300 = 2 2 * 3 * 5 2 ; 1260 = 2 2 * 3 2 *5 *7.
2) NOC = 6300.
That’s the whole problem, if you try to calculate the required number by multiplication, then the answer will definitely not be correct, since 300 * 1260 = 378,000.
Examination:
6300 / 300 = 21 - correct;
6300 / 1260 = 5 - correct.
The correctness of the result obtained is determined by checking - dividing the LCM by both original numbers; if the number is an integer in both cases, then the answer is correct.
What does NOC mean in mathematics?
As you know, there is not a single useless function in mathematics, this one is no exception. The most common purpose of this number is to reduce fractions to a common denominator. What is usually studied in grades 5-6 of secondary school. It is also additionally a common divisor for all multiples, if such conditions are present in the problem. Such an expression can find a multiple not only of two numbers, but also of a much larger number - three, five, and so on. The more numbers, the more actions in the task, but the complexity does not increase.
For example, given the numbers 250, 600 and 1500, you need to find their common LCM:
1) 250 = 25 * 10 = 5 2 *5 * 2 = 5 3 * 2 - this example describes factorization in detail, without reduction.
2) 600 = 60 * 10 = 3 * 2 3 *5 2 ;
3) 1500 = 15 * 100 = 33 * 5 3 *2 2 ;
In order to compose an expression, it is necessary to mention all the factors, in this case 2, 5, 3 are given - for all these numbers it is necessary to determine the maximum degree.
Attention: all factors must be brought to the point of complete simplification, if possible, decomposed to the level of single digits.
Examination:
1) 3000 / 250 = 12 - correct;
2) 3000 / 600 = 5 - true;
3) 3000 / 1500 = 2 - correct.
This method does not require any tricks or genius level abilities, everything is simple and clear.
Another way
In mathematics, many things are connected, many things can be solved in two or more ways, the same goes for finding the least common multiple, LCM. The following method can be used in the case of simple two-digit and single-digit numbers. A table is compiled into which the multiplicand is entered vertically, the multiplier horizontally, and the product is indicated in the intersecting cells of the column. You can reflect the table using a line, take a number and write down the results of multiplying this number by integers, from 1 to infinity, sometimes 3-5 points are enough, the second and subsequent numbers undergo the same computational process. Everything happens until a common multiple is found.
Given the numbers 30, 35, 42, you need to find the LCM connecting all the numbers:
1) Multiples of 30: 60, 90, 120, 150, 180, 210, 250, etc.
2) Multiples of 35: 70, 105, 140, 175, 210, 245, etc.
3) Multiples of 42: 84, 126, 168, 210, 252, etc.
It is noticeable that all the numbers are quite different, the only common number among them is 210, so it will be the NOC. Among the processes involved in this calculation there is also a greatest common divisor, which is calculated according to similar principles and is often encountered in neighboring problems. The difference is small, but quite significant, LCM involves calculating the number that is divided by all given initial values, and GCD involves calculating the largest value by which the original numbers are divided.
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.
The 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 go sailing 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
Let's start studying the least common multiple of two or more numbers. In this section we will define the term, consider the theorem that establishes the connection between the least common multiple and the greatest common divisor, and give examples of solving problems.
Common multiples – definition, examples
In this topic, we will be interested only in common multiples of integers other than zero.
Definition 1
Common multiple of integers is an integer that is a multiple of all given numbers. In fact, it is any integer that can be divided by any of the given numbers.
The definition of common multiples refers to two, three, or more integers.
Example 1
According to the definition given above, the common multiples of the number 12 are 3 and 2. Also, the number 12 will be a common multiple of the numbers 2, 3 and 4. The numbers 12 and -12 are common multiples of the numbers ±1, ±2, ±3, ±4, ±6, ±12.
At the same time, the common multiple of numbers 2 and 3 will be the numbers 12, 6, − 24, 72, 468, − 100,010,004 and a whole series of others.
If we take numbers that are divisible by the first number of a pair and not divisible by the second, then such numbers will not be common multiples. So, for numbers 2 and 3, the numbers 16, − 27, 5009, 27001 will not be common multiples.
0 is a common multiple of any set of integers other than zero.
If we recall the property of divisibility with respect to opposite numbers, it turns out that some integer k will be a common multiple of these numbers, just like the number - k. This means that common divisors can be either positive or negative.
Is it possible to find the LCM for all numbers?
The common multiple can be found for any integer.
Example 2
Suppose we are given k integers a 1 , a 2 , … , a k. The number we get when multiplying numbers a 1 · a 2 · … · a k according to the property of divisibility, it will be divided into each of the factors that were included in the original product. This means that the product of numbers a 1 , a 2 , … , a k is the least common multiple of these numbers.
How many common multiples can these integers have?
A group of integers can have a large number of common multiples. In fact, their number is infinite.
Example 3
Suppose we have some number k. Then the product of the numbers k · z, where z is an integer, will be a common multiple of the numbers k and z. Given that the number of numbers is infinite, the number of common multiples is infinite.
Least Common Multiple (LCM) – Definition, Notation and Examples
Recall the concept of the smallest number from a given set of numbers, which we discussed in the section “Comparing Integers.” Taking this concept into account, we formulate the definition of the least common multiple, which has the greatest practical significance among all common multiples.
Definition 2
Least common multiple of given integers is the smallest positive common multiple of these numbers.
A least common multiple exists for any number of given numbers. The most commonly used abbreviation for the concept in reference literature is NOC. Short notation for least common multiple of numbers a 1 , a 2 , … , a k will have the form LOC (a 1 , a 2 , … , a k).
Example 4
The least common multiple of 6 and 7 is 42. Those. LCM(6, 7) = 42. The least common multiple of the four numbers 2, 12, 15 and 3 is 60. A short notation will look like LCM (- 2, 12, 15, 3) = 60.
The least common multiple is not obvious for all groups of given numbers. Often it has to be calculated.
Relationship between NOC and GCD
The least common multiple and the greatest common divisor are related. The relationship between concepts is established by the theorem.
Theorem 1
The least common multiple of two positive integers a and b is equal to the product of a and b divided by the greatest common divisor of a and b, that is, LCM (a, b) = a · b: GCD (a, b).
Evidence 1
Suppose we have some number M, which is a multiple of the numbers a and b. If the number M is divisible by a, there also exists some integer z , under which the equality is true M = a k. According to the definition of divisibility, if M is divisible by b, so then a · k divided by b.
If we introduce a new notation for gcd (a, b) as d, then we can use the equalities a = a 1 d and b = b 1 · d. In this case, both equalities will be relatively prime numbers.
We have already established above that a · k divided by b. Now this condition can be written as follows:
a 1 d k divided by b 1 d, which is equivalent to the condition a 1 k divided by b 1 according to the properties of divisibility.
According to the property of coprime numbers, if a 1 And b 1– coprime numbers, a 1 not divisible by b 1 despite the fact that a 1 k divided by b 1, That b 1 must be shared k.
In this case, it would be appropriate to assume that there is a number t, for which k = b 1 t, and since b 1 = b: d, That k = b: d t.
Now instead of k let's substitute into equality M = a k expression of the form b: d t. This allows us to achieve equality M = a b: d t. At t = 1 we can get the least positive common multiple of a and b , equal a b: d, provided that numbers a and b positive.
So we proved that LCM (a, b) = a · b: GCD (a, b).
Establishing a connection between LCM and GCD allows you to find the least common multiple through the greatest common divisor of two or more given numbers.
Definition 3
The theorem has two important consequences:
- multiples of the least common multiple of two numbers are the same as the common multiples of those two numbers;
- the least common multiple of mutually prime positive numbers a and b is equal to their product.
It is not difficult to substantiate these two facts. Any common multiple of M of numbers a and b is defined by the equality M = LCM (a, b) · t for some integer value t. Since a and b are relatively prime, then gcd (a, b) = 1, therefore, gcd (a, b) = a · b: gcd (a, b) = a · b: 1 = a · b.
Least common multiple of three or more numbers
In order to find the least common multiple of several numbers, it is necessary to sequentially find the LCM of two numbers.
Theorem 2
Let's pretend that a 1 , a 2 , … , a k are some positive integers. In order to calculate the LCM m k these numbers, we need to sequentially calculate m 2 = LCM(a 1 , a 2) , m 3 = NOC(m 2 , a 3) , … , m k = NOC(m k - 1 , a k) .
Evidence 2
The first corollary from the first theorem discussed in this topic will help us prove the validity of the second theorem. The reasoning is based on the following algorithm:
- common multiples of numbers a 1 And a 2 coincide with multiples of their LCM, in fact, they coincide with multiples of the number m 2;
- common multiples of numbers a 1, a 2 And a 3 m 2 And a 3 m 3;
- common multiples of numbers a 1 , a 2 , … , a k coincide with common multiples of numbers m k - 1 And a k, therefore, coincide with multiples of the number m k;
- due to the fact that the smallest positive multiple of the number m k is the number itself m k, then the least common multiple of the numbers a 1 , a 2 , … , a k is m k.
This is how we proved the theorem.
If you notice an error in the text, please highlight it and press Ctrl+Enter
Loading...
