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 largest natural number by which numbers a and b are divided without remainder is called greatest common divisor these numbers. Denote GCD(a, b).
Let's consider finding GCD using the example of two natural numbers 18 and 60:
18 = 2×3×3
60 = 2 × 2 × 3 × 5
18 = 2×3×3
60 = 2 × 2 × 3 × 5
324 , 111 And 432
Let's factor the numbers into prime factors:
324 = 2 × 2 × 3 × 3 × 3 × 3
111 = 3×37
432 = 2 × 2 × 2 × 2 × 3 × 3 × 3
Crossing out from the first number the factors of which are not in the second and third numbers, we get:
2 × 2 × 2 × 2 × 3 × 3 × 3 = 3
As a result, GCD( 324 , 111 , 432 )=3
Finding GCD using the Euclidean algorithm
The second way to find the greatest common divisor is using Euclidean algorithm. The Euclidean algorithm is the most efficient way to find GCD, using it you need to constantly find the remainder of dividing numbers and apply recurrence formula.
Recurrence formula for GCD, GCD(a, b)=GCD(b, a mod b), where a mod b is the remainder of a divided by b.
Euclid's algorithm
Example Find the greatest common divisor of numbers 7920 And 594
Let's find GCD( 7920 , 594 ) using the Euclidean algorithm, we will calculate the remainder of division using a calculator.
- 7920 mod 594 = 7920 - 13 × 594 = 198
- 594 mod 198 = 594 – 3 × 198 = 0
As a result, we get GCD( 7920 , 594 ) = 198
Least common multiple
In order to find a common denominator when adding and subtracting fractions with different denominators, you need to know and be able to calculate least common multiple(NOK).
A multiple of the number “a” is a number that is itself divisible by the number “a” without a remainder.
Numbers that are multiples of 8 (that is, these numbers are divisible by 8 without a remainder): these are the numbers 16, 24, 32...
Multiples of 9: 18, 27, 36, 45…
There are infinitely many multiples of a given number a, in contrast to the divisors of the same number. There is a finite number of divisors.
The common multiple of two natural numbers is a number that is divisible by both of these numbers..
Least common multiple(LCM) of two or more natural numbers is the smallest natural number that is itself divisible by each of these numbers.
How to find NOC
LCM can be found and written in two ways.
The first way to find the LOC
This method is usually used for small numbers.
- We write down the multiples for each number on a line until we find a multiple that is the same for both numbers.
- The multiple of the number “a” is denoted by the capital letter “K”.
Example. Find LCM 6 and 8.
The second way to find the LOC
This method is convenient to use to find the LCM for three or more numbers.
The number of identical factors in decompositions of numbers can be different.
LCM(24, 60) = 2 2 3 5 2
Answer: LCM (24, 60) = 120
You can also formalize finding the least common multiple (LCM) as follows. Let's find the LOC (12, 16, 24).
24 = 2 2 2 3
As we see from the decomposition of numbers, all factors of 12 are included in the decomposition of 24 (the largest of the numbers), so we add only one 2 from the decomposition of the number 16 to the LCM.
LCM (12, 16, 24) = 2 2 2 3 2 = 48
Answer: LCM (12, 16, 24) = 48
Special cases of finding an NOC
For example, LCM (60, 15) = 60
Since coprime numbers have no common prime factors, their least common multiple is equal to the product of these numbers.
On our website you can also use a special calculator to find the least common multiple online to check your calculations.
If a natural number is divisible only by 1 and itself, then it is called prime.
Any natural number is always divisible by 1 and itself.
The number 2 is the smallest prime number. This is the only even prime number, the rest of the prime numbers are odd.
There are many prime numbers, and the first among them is the number 2. However, there is no last prime number. In the “For Study” section you can download a table of prime numbers up to 997.
But many natural numbers are also divisible by other natural numbers.
- the number 12 is divisible by 1, by 2, by 3, by 4, by 6, by 12;
- The number 36 is divisible by 1, by 2, by 3, by 4, by 6, by 12, by 18, by 36.
- decompose the divisors of numbers into prime factors;
The numbers by which the number is divisible by a whole (for 12 these are 1, 2, 3, 4, 6 and 12) are called the divisors of the number.
The divisor of a natural number a is a natural number that divides the given number “a” without a remainder.
A natural number that has more than two divisors is called composite.
Please note that the numbers 12 and 36 have common factors. These numbers are: 1, 2, 3, 4, 6, 12. The greatest divisor of these numbers is 12.
The common divisor of two given numbers “a” and “b” is the number by which both given numbers “a” and “b” are divided without remainder.
Greatest common divisor(GCD) of two given numbers “a” and “b” is the largest number by which both numbers “a” and “b” are divisible without a remainder.
Briefly, the greatest common divisor of the numbers “a” and “b” is written as follows::
Example: gcd (12; 36) = 12.
Divisors of numbers in the solution record are denoted by the capital letter “D”.
The numbers 7 and 9 have only one common divisor - the number 1. Such numbers are called coprime numbers.
Coprime numbers- these are natural numbers that have only one common divisor - the number 1. Their gcd is 1.
How to find the greatest common divisor
To find the gcd of two or more natural numbers you need:
It is convenient to write calculations using a vertical bar. To the left of the line we first write down the dividend, to the right - the divisor. Next, in the left column we write down the values of the quotients.
Let's explain it right away with an example. Let's factor the numbers 28 and 64 into prime factors.
- We emphasize the same prime factors in both numbers.
28 = 2 2 7
64 = 2 2 2 2 2 2
Find the product of identical prime factors and write down the answer;
GCD (28; 64) = 2 2 = 4
Answer: GCD (28; 64) = 4
You can formalize the location of the GCD in two ways: in a column (as done above) or “in a row”.
The first way to write gcd
Find gcd 48 and 36.
GCD (48; 36) = 2 2 3 = 12
The second way to write gcd
Now let's write down the solution to the GCD search in a line. Find gcd 10 and 15.
On our information site you can also use the Greatest Common Divisor online helper to check your calculations.
Finding the least common multiple, methods, examples of finding the LCM.
The material presented below is a logical continuation of the theory from the article entitled LCM - least common multiple, definition, examples, connection between LCM and GCD. Here we will talk about finding the least common multiple (LCM), and we will pay special attention to solving examples. First, we will show how the LCM of two numbers is calculated using the GCD of these numbers. Next, we'll look at finding the least common multiple by factoring numbers into prime factors. After this, we will focus on finding the LCM of three or more numbers, and also pay attention to calculating the LCM of negative numbers.
Page navigation.
Calculating Least Common Multiple (LCM) via GCD
One way to find the least common multiple is based on the relationship between LCM and GCD. The existing connection between LCM and GCD allows us to calculate the least common multiple of two positive integers through a known greatest common divisor. The corresponding formula is LCM(a, b)=a b:GCD(a, b). Let's look at examples of finding the LCM using the given formula.
Find the least common multiple of two numbers 126 and 70.
In this example a=126 , b=70 . Let's use the connection between LCM and GCD, expressed by the formula LCM(a, b)=a·b:GCD(a, b) . That is, first we have to find the greatest common divisor of the numbers 70 and 126, after which we can calculate the LCM of these numbers using the written formula.
Let's find GCD(126, 70) using the Euclidean algorithm: 126=70·1+56, 70=56·1+14, 56=14·4, therefore, GCD(126, 70)=14.
Now we find the required least common multiple: LCM(126, 70)=126·70:GCD(126, 70)= 126·70:14=630.
What is LCM(68, 34) equal to?
Since 68 is divisible by 34, then GCD(68, 34)=34. Now we calculate the least common multiple: LCM(68, 34)=68·34:GCD(68, 34)= 68·34:34=68.
Note that the previous example fits the following rule for finding the LCM for positive integers a and b: if a is divisible by b, then the least common multiple of these numbers is a.
Finding the LCM by factoring numbers into prime factors
Another way to find the least common multiple is based on factoring numbers into prime factors. If you compose a product from all the prime factors of given numbers, and then exclude from this product all the common prime factors present in the decompositions of the given numbers, then the resulting product will be equal to the least common multiple of the given numbers.
The stated rule for finding the LCM follows from the equality LCM(a, b)=a·b:GCD(a, b) . Indeed, the product of numbers a and b is equal to the product of all factors involved in the expansion of numbers a and b. In turn, GCD(a, b) is equal to the product of all prime factors simultaneously present in the expansions of numbers a and b (as described in the section on finding GCD using the expansion of numbers into prime factors).
Let's give an example. Let us know that 75=3·5·5 and 210=2·3·5·7. Let's compose the product from all the factors of these expansions: 2·3·3·5·5·5·7 . Now from this product we exclude all the factors present in both the expansion of the number 75 and the expansion of the number 210 (these factors are 3 and 5), then the product will take the form 2·3·5·5·7. The value of this product is equal to the least common multiple of the numbers 75 and 210, that is, LCM(75, 210)= 2·3·5·5·7=1050.
Factor the numbers 441 and 700 into prime factors and find the least common multiple of these numbers.
Let's factor the numbers 441 and 700 into prime factors: 
We get 441=3·3·7·7 and 700=2·2·5·5·7.
Now let’s create a product from all the factors involved in the expansion of these numbers: 2·2·3·3·5·5·7·7·7. Let us exclude from this product all factors that are simultaneously present in both expansions (there is only one such factor - this is the number 7): 2·2·3·3·5·5·7·7. Thus, LCM(441, 700)=2·2·3·3·5·5·7·7=44 100 .
NOC(441, 700)= 44 100 .
The rule for finding the LCM using factorization of numbers into prime factors can be formulated a little differently. If the missing factors from the expansion of number b are added to the factors from the expansion of the number a, then the value of the resulting product will be equal to the least common multiple of the numbers a and b.
For example, let's take the same numbers 75 and 210, their decompositions into prime factors are as follows: 75=3·5·5 and 210=2·3·5·7. To the factors 3, 5 and 5 from the expansion of the number 75 we add the missing factors 2 and 7 from the expansion of the number 210, we obtain the product 2·3·5·5·7, the value of which is equal to LCM(75, 210).
Find the least common multiple of 84 and 648.
We first obtain the decompositions of the numbers 84 and 648 into prime factors. They look like 84=2·2·3·7 and 648=2·2·2·3·3·3·3. To the factors 2, 2, 3 and 7 from the expansion of the number 84 we add the missing factors 2, 3, 3 and 3 from the expansion of the number 648, we obtain the product 2 2 2 3 3 3 3 7, which is equal to 4 536 . Thus, the desired least common multiple of 84 and 648 is 4,536.
Finding the LCM of three or more numbers
The least common multiple of three or more numbers can be found by sequentially finding the LCM of two numbers. Let us recall the corresponding theorem, which gives a way to find the LCM of three or more numbers.
Let positive integer numbers a 1 , a 2 , …, a k be given, the least common multiple m k of these numbers is found by sequentially calculating m 2 = LCM(a 1 , a 2) , m 3 = LCM(m 2 , a 3) , … , m k = LCM(m k−1 , a k) .
Let's consider the application of this theorem using the example of finding the least common multiple of four numbers.
Find the LCM of four numbers 140, 9, 54 and 250.
First we find m 2 = LCM(a 1 , a 2) = LCM(140, 9) . To do this, using the Euclidean algorithm, we determine GCD(140, 9), we have 140=9·15+5, 9=5·1+4, 5=4·1+1, 4=1·4, therefore, GCD(140, 9)=1, from which LCM(140, 9)=140·9:GCD(140, 9)= 140·9:1=1,260. That is, m 2 =1 260.
Now we find m 3 = LCM(m 2 , a 3) = LCM(1 260, 54). Let's calculate it through GCD(1 260, 54), which we also determine using the Euclidean algorithm: 1 260=54·23+18, 54=18·3. Then gcd(1,260, 54)=18, from which gcd(1,260, 54)= 1,260·54:gcd(1,260, 54)= 1,260·54:18=3,780. That is, m 3 =3 780.
It remains to find m 4 = LCM(m 3 , a 4) = LCM(3 780, 250). To do this, we find GCD(3,780, 250) using the Euclidean algorithm: 3,780=250·15+30, 250=30·8+10, 30=10·3. Therefore, GCD(3,780, 250)=10, from which GCD(3,780, 250)= 3,780·250:GCD(3,780, 250)= 3,780·250:10=94,500. That is, m 4 =94,500.
So the least common multiple of the original four numbers is 94,500.
LCM(140, 9, 54, 250)=94,500 .
In many cases, it is convenient to find the least common multiple of three or more numbers using prime factorizations of the given numbers. In this case, you should adhere to the following rule. The least common multiple of several numbers is equal to the product, which is composed as follows: the missing factors from the expansion of the second number are added to all the factors from the expansion of the first number, the missing factors from the expansion of the third number are added to the resulting factors, and so on.
Let's look at an example of finding the least common multiple using prime factorization.
Find the least common multiple of the five numbers 84, 6, 48, 7, 143.
First, we obtain decompositions of these numbers into prime factors: 84=2·2·3·7, 6=2·3, 48=2·2·2·2·3, 7 (7 is a prime number, it coincides with its decomposition into prime factors) and 143=11·13.
To find the LCM of these numbers, to the factors of the first number 84 (they are 2, 2, 3 and 7), you need to add the missing factors from the expansion of the second number 6. The decomposition of the number 6 does not contain missing factors, since both 2 and 3 are already present in the decomposition of the first number 84. Next, to the factors 2, 2, 3 and 7 we add the missing factors 2 and 2 from the expansion of the third number 48, we get a set of factors 2, 2, 2, 2, 3 and 7. There will be no need to add multipliers to this set in the next step, since 7 is already contained in it. Finally, to the factors 2, 2, 2, 2, 3 and 7 we add the missing factors 11 and 13 from the expansion of the number 143. We get the product 2·2·2·2·3·7·11·13, which is equal to 48,048.
Therefore, LCM(84, 6, 48, 7, 143)=48,048.
LCM(84, 6, 48, 7, 143)=48,048 .
Finding the least common multiple of negative numbers
Sometimes there are tasks in which you need to find the least common multiple of numbers, among which one, several or all numbers are negative. In these cases, all negative numbers must be replaced by their opposite numbers, and then the LCM of positive numbers must be found. This is the way to find the LCM of negative numbers. For example, LCM(54, −34) = LCM(54, 34) and LCM(−622, −46, −54, −888) = LCM(622, 46, 54, 888) .
We can do this because the set of multiples of a is the same as the set of multiples of −a (a and −a are opposite numbers). Indeed, let b be some multiple of a, then b is divisible by a, and the concept of divisibility states the existence of an integer q such that b=a·q. But the equality b=(−a)·(−q) will also be true, which, due to the same concept of divisibility, means that b is divisible by −a, that is, b is a multiple of −a. The converse is also true: if b is some multiple of −a, then b is also a multiple of a.
Find the least common multiple of negative numbers −145 and −45.
Let's replace the negative numbers −145 and −45 with their opposite numbers 145 and 45. We have LCM(−145, −45) = LCM(145, 45) . Having determined GCD(145, 45)=5 (for example, using the Euclidean algorithm), we calculate GCM(145, 45)=145·45:GCD(145, 45)= 145·45:5=1 305 . Thus, the least common multiple of the negative integers −145 and −45 is 1,305.
www.cleverstudents.ru
We continue to study division. In this lesson we will look at concepts such as GCD And NOC.
GCD is the greatest common divisor.
NOC is the least common multiple.
The topic is quite boring, but you definitely need to understand it. Without understanding this topic, you will not be able to work effectively with fractions, which are a real obstacle in mathematics.
Greatest common divisor
Definition. Greatest common divisor of numbers a And b a And b divided without remainder.
To understand this definition well, let’s substitute for the variables a And b any two numbers, for example, instead of a variable a Let's substitute the number 12, and instead of the variable b number 9. Now let's try to read this definition:
Greatest common divisor of numbers 12 And 9 is called the largest number by which 12 And 9 divided without remainder.
From the definition it is clear that we are talking about the common divisor of the numbers 12 and 9, and this divisor is the largest of all existing divisors. This greatest common divisor (GCD) needs to be found.
To find the greatest common divisor of two numbers, three methods are used. The first method is quite labor-intensive, but it allows you to clearly understand the essence of the topic and feel its full meaning.
The second and third methods are quite simple and make it possible to quickly find a GCD. We will look at all three methods. And which one to use in practice is up to you to choose.
The first method is to find all possible divisors of two numbers and choose the largest one. Let's look at this method using the following example: find the greatest common divisor of the numbers 12 and 9.
First, we will find all possible divisors of the number 12. To do this, we will divide 12 by all divisors in the range from 1 to 12. If the divisor allows us to divide 12 without a remainder, then we will highlight it in blue and make an appropriate explanation in parentheses.
12: 1 = 12
(12 is divided by 1 without a remainder, which means 1 is a divisor of the number 12)
12: 2 = 6
(12 is divided by 2 without a remainder, which means 2 is a divisor of the number 12)
12: 3 = 4
(12 is divided by 3 without a remainder, which means 3 is a divisor of the number 12)
12: 4 = 3
(12 is divided by 4 without a remainder, which means 4 is a divisor of the number 12)
12: 5 = 2 (2 left over)
(12 is not divided by 5 without a remainder, which means 5 is not a divisor of the number 12)
12: 6 = 2
(12 is divided by 6 without a remainder, which means 6 is a divisor of the number 12)
12: 7 = 1 (5 leftover)
(12 is not divided by 7 without a remainder, which means 7 is not a divisor of the number 12)
12: 8 = 1 (4 leftover)
(12 is not divided by 8 without a remainder, which means 8 is not a divisor of 12)
12: 9 = 1 (3 leftover)
(12 is not divided by 9 without a remainder, which means 9 is not a divisor of the number 12)
12: 10 = 1 (2 leftover)
(12 is not divided by 10 without a remainder, which means 10 is not a divisor of the number 12)
12: 11 = 1 (1 leftover)
(12 is not divided by 11 without a remainder, which means 11 is not a divisor of 12)
12: 12 = 1
(12 is divided by 12 without a remainder, which means 12 is a divisor of the number 12)
Now let’s find the divisors of the number 9. To do this, check all the divisors from 1 to 9
9: 1 = 9
(9 is divided by 1 without a remainder, which means 1 is a divisor of the number 9)
9: 2 = 4 (1 leftover)
(9 is not divided by 2 without a remainder, which means 2 is not a divisor of the number 9)
9: 3 = 3
(9 is divided by 3 without a remainder, which means 3 is a divisor of the number 9)
9: 4 = 2 (1 leftover)
(9 is not divided by 4 without a remainder, which means 4 is not a divisor of the number 9)
9: 5 = 1 (4 leftover)
(9 is not divided by 5 without a remainder, which means 5 is not a divisor of the number 9)
9: 6 = 1 (3 leftover)
(9 is not divided by 6 without a remainder, which means 6 is not a divisor of the number 9)
9: 7 = 1 (2 leftover)
(9 is not divided by 7 without a remainder, which means 7 is not a divisor of the number 9)
9: 8 = 1 (1 leftover)
(9 is not divided by 8 without a remainder, which means 8 is not a divisor of the number 9)
9: 9 = 1
(9 is divided by 9 without a remainder, which means 9 is a divisor of the number 9)
Now let's write down the divisors of both numbers. The numbers highlighted in blue are divisors. Let's write them down:
Having written out the divisors, you can immediately determine which is the largest and most common.
By definition, the greatest common divisor of the numbers 12 and 9 is the number that divides 12 and 9 without a remainder. The greatest and common divisor of the numbers 12 and 9 is the number 3
Both the number 12 and the number 9 are divisible by 3 without a remainder:
So gcd (12 and 9) = 3
The second way to find GCD
Now let's look at the second method of finding the greatest common divisor. The essence of this method is to decompose both numbers into prime factors and multiply the common ones.
Example 1. Find the gcd of numbers 24 and 18
First, let's factor both numbers into prime factors:
Now let's multiply their common factors. To avoid confusion, common factors can be emphasized.
We look at the expansion of the number 24. Its first factor is 2. We look for the same factor in the expansion of the number 18 and see that it is there too. We emphasize both twos:
We look again at the expansion of the number 24. Its second factor is also 2. We look for the same factor in the expansion of the number 18 and see that for the second time it is no longer there. Then we don’t emphasize anything.
The next two in the expansion of the number 24 is also absent in the expansion of the number 18.
Let's move on to the last factor in the expansion of the number 24. This is factor 3. We look for the same factor in the expansion of the number 18 and see that it is there too. We emphasize both threes:
So, the common factors of the numbers 24 and 18 are the factors 2 and 3. To get GCD, these factors must be multiplied:
So gcd (24 and 18) = 6
The third way to find GCD
Now let's look at the third way to find the greatest common divisor. The essence of this method is that the numbers to be found for the greatest common divisor are decomposed into prime factors. Then, from the expansion of the first number, factors that are not included in the expansion of the second number are crossed out. The remaining numbers in the first expansion are multiplied and obtained GCD.
For example, let's find GCD for the numbers 28 and 16 using this method. First of all, we decompose these numbers into prime factors:
We got two expansions: and
Now from the decomposition of the first number we will delete the factors that are not included in the decomposition of the second number. The expansion of the second number does not include seven. Let’s cross it out from the first expansion:
Now we multiply the remaining factors and get GCD:
The number 4 is the greatest common divisor of the numbers 28 and 16. Both of these numbers are divisible by 4 without a remainder:
Example 2. Find the gcd of numbers 100 and 40
Factoring the number 100
Factoring the number 40
We got two expansions:
Now from the decomposition of the first number we will delete the factors that are not included in the decomposition of the second number. The expansion of the second number does not include one five (there is only one five). Let’s cross it out from the first expansion
Let's multiply the remaining numbers:
We received the answer 20. This means that the number 20 is the greatest common divisor of the numbers 100 and 40. These two numbers are divisible by 20 without a remainder:
GCD (100 and 40) = 20.
Example 3. Find the gcd of numbers 72 and 128
Factoring the number 72
Factoring the number 128
2 × 2 × 2 × 2 × 2 × 2 × 2
Now from the decomposition of the first number we will delete the factors that are not included in the decomposition of the second number. The expansion of the second number does not include two triplets (they are not there at all). Let’s cross them out from the first expansion:
We received the answer 8. This means that the number 8 is the greatest common divisor of the numbers 72 and 128. These two numbers are divisible by 8 without a remainder:
GCD (72 and 128) = 8
Finding GCD for several numbers
The greatest common divisor can be found for several numbers, not just two. To do this, the numbers to be found for the greatest common divisor are decomposed into prime factors, then the product of the common prime factors of these numbers is found.
For example, let's find GCD for the numbers 18, 24 and 36
Let's factorize the number 18
Let's factorize the number 24
Let's factorize the number 36
We got three expansions:
Now let's highlight and underline the common factors in these numbers. Common factors must appear in all three numbers:
We see that the common factors for the numbers 18, 24 and 36 are the factors 2 and 3. Multiplying these factors, we get the gcd we are looking for:
We received the answer 6. This means that the number 6 is the greatest common divisor of the numbers 18, 24 and 36. These three numbers are divisible by 6 without a remainder:
GCD (18, 24 and 36) = 6
Example 2. Find GCD for numbers 12, 24, 36 and 42
Let's factor each number into prime factors. Then we find the product of the common factors of these numbers.
Let's factorize the number 12
Let's factorize the number 42
We got four expansions:
Now let's highlight and underline the common factors in these numbers. Common factors must appear in all four numbers:
We see that the common factors for the numbers 12, 24, 36, and 42 are the factors of 2 and 3. Multiplying these factors together gives us the gcd we are looking for:
We received the answer 6. This means that the number 6 is the greatest common divisor of the numbers 12, 24, 36 and 42. These numbers are divisible by 6 without a remainder:
GCD (12, 24, 36 and 42) = 6
From the previous lesson we know that if a number is divided by another without a remainder, it is called a multiple of this number.
It turns out that several numbers can have a common multiple. And now we will be interested in the multiple of two numbers, and it should be as small as possible.
Definition. Least common multiple (LCM) of numbers a And b- a And b a and number b.
Definition contains two variables a And b. Let's substitute any two numbers instead of these variables. For example, instead of a variable a Let's substitute the number 9, and instead of the variable b Let's substitute the number 12. Now let's try to read the definition:
Least common multiple (LCM) of numbers 9 And 12 - is the smallest number that is a multiple of 9 And 12 . In other words, this is such a small number that is divisible without a remainder by the number 9 and by number 12 .
From the definition it is clear that the LCM is the smallest number that is divisible by 9 and 12 without a remainder. This LCM needs to be found.
To find the least common multiple (LCM), you can use two methods. The first way is that you can write down the first multiples of two numbers, and then choose among these multiples a number that will be common to both numbers and small. Let's apply this method.
First of all, let's find the first multiples of the number 9. To find the multiples of 9, you need to multiply this nine one by one by numbers from 1 to 9. The resulting answers will be multiples of the number 9. So, let's begin. We will highlight multiples in red:
Now we find the multiples of the number 12. To do this, we multiply 12 one by one by all numbers 1 to 12.
Now and in what follows we will assume that at least one of these numbers is non-zero. If all given numbers are equal to zero, then their common divisor is any integer, and since there are infinitely many integers, we cannot talk about the greatest of them. Therefore, we cannot talk about the greatest common divisor of numbers, each of which is equal to zero.
Now we can give determining the greatest common divisor two numbers.
Definition.
Greatest common divisor two integers is the largest integer dividing two given integers.
To briefly write the greatest common divisor, the abbreviation GCD is often used - Greatest Common Divisor. Also, the greatest common divisor of two numbers a and b is often denoted as GCD(a, b) .
Let's give example of greatest common divisor (GCD) two integers. The greatest common divisor of the numbers 6 and −15 is 3. Let's justify this. Let's write down all the divisors of the number six: ±6, ±3, ±1, and the divisors of the number −15 are the numbers ±15, ±5, ±3 and ±1. Now you can find all the common divisors of the numbers 6 and −15, these are the numbers −3, −1, 1 and 3. Since −3<−1<1<3 , то 3 – это наибольший общий делитель чисел 6 и −15 . То есть, НОД(6, −15)=3 .
Determining the greatest common divisor of three or more integers is similar to determining the gcd of two numbers.
Definition.
Greatest common divisor three or more integers is the largest integer dividing all given numbers at the same time.
We will denote the greatest common divisor of n integers a 1 , a 2 , …, a n as GCD(a 1 , a 2 , …, a n) . If the value b of the greatest common divisor of these numbers is found, then we can write GCD(a 1 , a 2 , …, a n)=b.
As an example, let's give the gcd of four integers −8, 52, 16 and −12, it is equal to 4, that is, gcd(−8, 52, 16, −12)=4. This can be checked by writing down all the divisors of the given numbers, choosing common ones from them and determining the greatest common divisor.
Note that the greatest common divisor of integers can be equal to one of these numbers. This statement is true if all given numbers are divisible by one of them (the proof is given in the next paragraph of this article). For example, GCD(15, 60, −45)=15. This is true, since 15 divides both the number 15, and the number 60, and the number −45, and there is no common divisor of the numbers 15, 60 and −45 that exceeds 15.
Of particular interest are the so-called relatively prime numbers - those integers whose greatest common divisor is equal to one.
Properties of the greatest common divisor, Euclidean algorithm
The greatest common divisor has a number of characteristic results, in other words, a number of properties. Now we will list the main properties of the greatest common divisor (GCD), we will formulate them in the form of theorems and immediately provide proofs.
We will formulate all the properties of the greatest common divisor for positive integers, and we will consider only the positive divisors of these numbers.
The greatest common divisor of the numbers a and b is equal to the greatest common divisor of the numbers b and a , that is, gcd(a, b) = gcd(a, b) .
This property of GCD follows directly from the definition of the greatest common divisor.
If a is divisible by b, then the set of common divisors of the numbers a and b coincides with the set of divisors of the number b, in particular, gcd(a, b)=b.
Proof.
Any common divisor of the numbers a and b is a divisor of each of these numbers, including the number b. On the other hand, since a is a multiple of b, then any divisor of the number b is a divisor of the number a due to the fact that divisibility has the property of transitivity, therefore, any divisor of the number b is a common divisor of the numbers a and b. This proves that if a is divisible by b, then the set of divisors of the numbers a and b coincides with the set of divisors of one number b. And since the greatest divisor of the number b is the number b itself, then the greatest common divisor of the numbers a and b is also equal to b, that is, gcd(a, b)=b.
In particular, if the numbers a and b are equal, then gcd(a, b)=gcd(a, a)=gcd(b, b)=a=b. For example, GCD(132, 132)=132.
The proven property of the greatest divisor allows us to find the gcd of two numbers when one of them is divided by the other. In this case, GCD is equal to one of these numbers, which is divided by another number. For example, GCD(8, 24)=8, since 24 is a multiple of eight.
If a=b·q+c, where a, b, c and q are integers, then the set of common divisors of the numbers a and b coincides with the set of common divisors of the numbers b and c, in particular, gcd(a, b)=gcd (b, c) .
Let us justify this property of GCD.
Since the equality a=b·q+c holds, then every common divisor of the numbers a and b also divides c (this follows from the properties of divisibility). For the same reason, every common divisor of b and c divides a. Therefore, the set of common divisors of the numbers a and b coincides with the set of common divisors of the numbers b and c. In particular, the greatest of these common divisors must also coincide, that is, the following equality GCD(a, b) = GCD(b, c) must be true.
Now we will formulate and prove the theorem, which is Euclidean algorithm. The Euclid algorithm allows you to find the GCD of two numbers (see finding the GCD using the Euclid algorithm). Moreover, the Euclid algorithm will allow us to prove the following properties of the greatest common divisor.
Before giving the formulation of the theorem, we recommend refreshing your memory of the theorem from the theory section, which states that the dividend a can be represented as b q + r, where b is a divisor, q is some integer called an incomplete quotient, and r is an integer that satisfies the condition, called the remainder.
So, let a series of equalities be true for two non-zero positive integers a and b 
ending when r k+1 =0 (which is inevitable, since b>r 1 >r 2 >r 3 , ... is a series of decreasing integers, and this series cannot contain more than a finite number of positive numbers), then r k – this is the greatest common divisor of the numbers a and b, that is, r k = gcd(a, b) .
Proof.
Let us first prove that r k is a common divisor of the numbers a and b, after which we will show that r k is not just a divisor, but the greatest common divisor of the numbers a and b.
We will move along the written equalities from bottom to top. From the last equality we can say that r k−1 is divisible by r k . Taking into account this fact, as well as the previous property of GCD, the penultimate equality r k−2 =r k−1 ·q k +r k allows us to state that r k−2 is divisible by r k, since r k−1 is divisible by r k and r k is divisible by r k. By analogy, from the third equality from below we conclude that r k−3 is divisible by r k . And so on. From the second equality we obtain that b is divisible by r k , and from the first equality we obtain that a is divisible by r k . Therefore, r k is a common divisor of the numbers a and b.
It remains to prove that r k = GCD(a, b) . For it is enough to show that any common divisor of the numbers a and b (let’s denote it r 0 ) divides r k .
We will move along the original equalities from top to bottom. Due to the previous property, it follows from the first equality that r 1 is divisible by r 0 . Then from the second equality we obtain that r 2 is divisible by r 0 . And so on. From the last equality we obtain that r k is divisible by r 0 . Thus, r k = GCD(a, b) .
From the considered property of the greatest common divisor it follows that the set of common divisors of the numbers a and b coincides with the set of divisors of the greatest common divisor of these numbers. This corollary from Euclid's algorithm allows us to find all common divisors of two numbers as divisors of the gcd of these numbers.
Let a and b be integers that are not equal to zero at the same time, then there are integers u 0 and v 0, then the equality GCD(a, b)=a·u 0 +b·v 0 is true. The last equality is a linear representation of the greatest common divisor of the numbers a and b, this equality is called the Bezout relation, and the numbers u 0 and v 0 are called the Bezout coefficients.
Proof.
Using the Euclidean algorithm we can write the following equalities
From the first equality we have r 1 =a−b·q 1, and, denoting 1=s 1 and −q 1 =t 1, this equality takes the form r 1 =s 1 ·a+t 1 ·b, and the numbers s 1 and t 1 are integers. Then from the second equality we obtain r 2 =b−r 1 ·q 2 = b−(s 1 ·a+t 1 ·b)·q 2 =−s 1 ·q 2 ·a+(1−t 1 ·q 2)·b. Denoting −s 1 ·q 2 =s 2 and 1−t 1 ·q 2 =t 2, the last equality can be written as r 2 =s 2 ·a+t 2 ·b, and s 2 and t 2 are integers (since the sum, difference and product of integers is an integer). Similarly, from the third equality we obtain r 3 =s 3 ·a+t 3 ·b, from the fourth equality r 4 =s 4 ·a+t 4 ·b, and so on. Finally, r k =s k ·a+t k ·b, where s k and t k are integers. Since r k =GCD(a, b) , and denoting s k =u 0 and t k =v 0 , we obtain a linear representation of GCD of the required form: GCD(a, b)=a·u 0 +b·v 0 .
If m is any natural number, then GCD(m a, m b)=m GCD(a, b).
The rationale for this property of the greatest common divisor is as follows. If we multiply by m both sides of each of the equalities of the Euclidean algorithm, we obtain that GCD(m·a, m·b)=m·r k , and r k is GCD(a, b) . Hence, GCD(m a, m b)=m GCD(a, b).
The method of finding GCD using prime factorization is based on this property of the greatest common divisor.
Let p be any common divisor of numbers a and b, then gcd(a:p, b:p)=gcd(a, b):p, in particular, if p=GCD(a, b) we have gcd(a:gcd(a, b), b:gcd(a, b))=1, that is, the numbers a:GCD(a, b) and b:GCD(a, b) are relatively prime.
Since a=p·(a:p) and b=p·(b:p) , and due to the previous property, we can write a chain of equalities of the form GCD(a, b)=GCD(p (a:p), p (b:p))= p·GCD(a:p, b:p) , from which the equality being proved follows.
The property of the greatest common divisor that we just proved is the basis of .
Now we will voice the GCD property, which reduces the problem of finding the greatest common divisor of three or more numbers to sequentially finding the GCD of two numbers.
The greatest common divisor of the numbers a 1 , a 2 , …, a k is 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 .
The proof is based on a corollary of the Euclidean algorithm. The common divisors of the numbers a 1 and a 2 coincide with the divisors of d 2. Then the common divisors of the numbers a 1, a 2 and a 3 coincide with the common divisors of the numbers d 2 and a 3, therefore, they coincide with the divisors of d 3. The common divisors of the numbers a 1, a 2, a 3 and a 4 coincide with the common divisors of d 3 and a 4, therefore, they coincide with the divisors of d 4. And so on. Finally, the common divisors of the numbers a 1, a 2, ..., a k coincide with the divisors d k. And since the greatest divisor of the number d k is the number d k itself, then GCD(a 1 , a 2 , …, a k)=d k.
This concludes our review of the basic properties of the greatest common divisor.
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.
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 whole objects.
If a natural number can only be divided into 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 odd numbers can be prime.
There are quite a lot of prime numbers; there is no complete list of them. To find 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 another 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 factors, it is called composite.
The number 30 can have divisors such as 1, 3, 5, 6, 15, 30.
You will notice 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 they can be divided entirely. The largest can be considered the maximum total number by 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 the divisors of a natural number, use the notation:
D (15) = (1, 3, 5, 15)
GCD (9; 15) = 1
In this example, the natural numbers have only one common divisor. They are called relatively prime, so unity 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, factor them into factors (prime numbers);
Select all identical factors of given numbers;
Multiply them together.
For example, to calculate the greatest common divisor of the numbers 30 and 56, you would write the following:
To avoid confusion, it is convenient to write factors using vertical columns. On the left side of the line you need to place the dividend, and on the right side - the divisor. Under the dividend you should indicate the resulting quotient.
So, in the right column there will be all the factors needed for the solution.
Identical divisors (found factors) can be underlined for convenience. They should be rewritten and multiplied and the greatest common divisor written down.
GCD (30; 56) = 2 * 5 = 10
This is how easy it really is to find the greatest common divisor of numbers. If you practice a little, you can do this almost automatically.
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:
- 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:
- Factor numbers into prime factors
- 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
- Any common multiple of $a$ and $b$ is divisible by K$(a;b)$
- 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)$