Largest common divisor
Definition 2
If 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 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 notations:
$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. To do 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 number divisors.
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)$
Second number: b=
Thousand separator Without space separator "´
Result:
Greatest common divisor gcd( a,b)=6
Least common multiple of LCM( a,b)=468
The largest natural number that can be divided without a remainder by numbers a and b is called greatest common divisor(GCD) of these numbers. Denoted by gcd(a,b), (a,b), gcd(a,b) or hcf(a,b).
Least common multiple The LCM of two integers a and b is the smallest natural number that is divisible by a and b without a remainder. Denoted LCM(a,b), or lcm(a,b).
The integers a and b are called mutually prime, if they have no common divisors other than +1 and −1.
Greatest common divisor
Let two positive numbers be given a 1 and a 2 1). It is required to find the common divisor of these numbers, i.e. find such a number λ , which divides numbers a 1 and a 2 at the same time. Let's describe the algorithm.
1) In this article, the word number will be understood as an integer.
Let a 1 ≥ a 2 and let
Where m 1 , a 3 are some integers, a 3 <a 2 (remainder of division a 1 per a 2 should be less a 2).
Let's assume that λ divides a 1 and a 2 then λ divides m 1 a 2 and λ divides a 1 −m 1 a 2 =a 3 (Statement 2 of the article “Divisibility of numbers. Divisibility test”). It follows that every common divisor a 1 and a 2 is the common divisor a 2 and a 3. The reverse is also true if λ common divisor a 2 and a 3 then m 1 a 2 and a 1 =m 1 a 2 +a 3 is also divisible by λ . Therefore the common divisor a 2 and a 3 is also a common divisor a 1 and a 2. Because a 3 <a 2 ≤a 1, then we can say that the solution to the problem of finding the common divisor of numbers a 1 and a 2 reduced to the simpler problem of finding the common divisor of numbers a 2 and a 3 .
If a 3 ≠0, then we can divide a 2 on a 3. Then
,
Where m 1 and a 4 are some integers, ( a 4 remainder from division a 2 on a 3 (a 4 <a 3)). By similar reasoning we come to the conclusion that common divisors of numbers a 3 and a 4 coincides with common divisors of numbers a 2 and a 3, and also with common divisors a 1 and a 2. Because a 1 , a 2 , a 3 , a 4, ... are numbers that are constantly decreasing, and since there is a finite number of integers between a 2 and 0, then at some step n, remainder of division a n on a n+1 will be equal to zero ( a n+2 =0).
.
Every common divisor λ numbers a 1 and a 2 is also a divisor of numbers a 2 and a 3 , a 3 and a 4 , .... a n and a n+1 . The converse is also true, common divisors of numbers a n and a n+1 are also divisors of numbers a n−1 and a n , .... , a 2 and a 3 , a 1 and a 2. But the common divisor of numbers a n and a n+1 is a number a n+1 , because a n and a n+1 are divisible by a n+1 (remember that a n+2 =0). Hence a n+1 is also a divisor of numbers a 1 and a 2 .
Note that the number a n+1 is the largest divisor of numbers a n and a n+1 , since the greatest divisor a n+1 is itself a n+1 . If a n+1 can be represented as a product of integers, then these numbers are also common divisors of numbers a 1 and a 2. Number a n+1 is called greatest common divisor numbers a 1 and a 2 .
Numbers a 1 and a 2 can be either positive or negative numbers. If one of the numbers is equal to zero, then the greatest common divisor of these numbers will be equal to the absolute value of the other number. The greatest common divisor of zero numbers is undefined.
The above algorithm is called Euclidean algorithm to find the greatest common divisor of two integers.
An example of finding the greatest common divisor of two numbers
Find the greatest common divisor of two numbers 630 and 434.
- Step 1. Divide the number 630 by 434. The remainder is 196.
- Step 2. Divide the number 434 by 196. The remainder is 42.
- Step 3. Divide the number 196 by 42. The remainder is 28.
- Step 4. Divide the number 42 by 28. The remainder is 14.
- Step 5. Divide the number 28 by 14. The remainder is 0.
In step 5, the remainder of the division is 0. Therefore, the greatest common divisor of the numbers 630 and 434 is 14. Note that the numbers 2 and 7 are also divisors of the numbers 630 and 434.
Coprime numbers
Definition 1. Let the greatest common divisor of the numbers a 1 and a 2 is equal to one. Then these numbers are called coprime numbers, having no common divisor.
Theorem 1. If a 1 and a 2 coprime numbers, and λ some number, then any common divisor of numbers λa 1 and a 2 is also a common divisor of numbers λ And a 2 .
Proof. Consider the Euclidean algorithm for finding the greatest common divisor of numbers a 1 and a 2 (see above).
.
From the conditions of the theorem it follows that the greatest common divisor of the numbers a 1 and a 2 and therefore a n and a n+1 is 1. That is a n+1 =1.
Let's multiply all these equalities by λ , Then
.
Let the common divisor a 1 λ And a 2 yes δ . Then δ is included as a multiplier in a 1 λ , m 1 a 2 λ and in a 1 λ -m 1 a 2 λ =a 3 λ (see "Divisibility of numbers", Statement 2). Next δ is included as a multiplier in a 2 λ And m 2 a 3 λ , and, therefore, is included as a factor in a 2 λ -m 2 a 3 λ =a 4 λ .
Reasoning this way, we are convinced that δ is included as a multiplier in a n−1 λ And m n−1 a n λ , and therefore in a n−1 λ −m n−1 a n λ =a n+1 λ . Because a n+1 =1, then δ is included as a multiplier in λ . Therefore the number δ is the common divisor of numbers λ And a 2 .
Let us consider special cases of Theorem 1.
Consequence 1. Let a And c Prime numbers are relatively b. Then their product ac is a prime number with respect to b.
Really. From Theorem 1 ac And b have the same common divisors as c And b. But the numbers c And b relatively simple, i.e. have a single common divisor 1. Then ac And b also have a single common divisor 1. Therefore ac And b mutually simple.
Consequence 2. Let a And b coprime numbers and let b divides ak. Then b divides and k.
Really. From the approval condition ak And b have a common divisor b. By virtue of Theorem 1, b must be a common divisor b And k. Hence b divides k.
Corollary 1 can be generalized.
Consequence 3. 1. Let the numbers a 1 , a 2 , a 3 , ..., a m are prime relative to the number b. Then a 1 a 2 , a 1 a 2 · a 3 , ..., a 1 a 2 a 3 ··· a m, the product of these numbers is prime with respect to the number b.
2. Let us have two rows of numbers
such that every number in the first series is prime in the ratio of every number in the second series. Then the product
You need to find numbers that are divisible by each of these numbers.
If a number is divisible by a 1, then it has the form sa 1 where s some number. If q is the greatest common divisor of numbers a 1 and a 2, then
Where s 1 is some integer. Then
is least common multiples of numbers a 1 and a 2 .
a 1 and a 2 are relatively prime, then the least common multiple of the numbers a 1 and a 2:
We need to find the least common multiple of these numbers.
From the above it follows that any multiple of numbers a 1 , a 2 , a 3 must be a multiple of numbers ε And a 3 and back. Let the least common multiple of the numbers ε And a 3 yes ε 1. Next, multiples of numbers a 1 , a 2 , a 3 , a 4 must be a multiple of numbers ε 1 and a 4. Let the least common multiple of the numbers ε 1 and a 4 yes ε 2. Thus, we found out that all multiples of numbers a 1 , a 2 , a 3 ,...,a m coincide with multiples of a certain number ε n, which is called the least common multiple of the given numbers.
In the special case when the numbers a 1 , a 2 , a 3 ,...,a m are relatively prime, then the least common multiple of the numbers a 1 , a 2, as shown above, has the form (3). Next, since a 3 prime in relation to numbers a 1 , a 2 then a 3 prime number a 1 · a 2 (Corollary 1). Means the least common multiple of the numbers a 1 ,a 2 ,a 3 is a number a 1 · a 2 · a 3. Reasoning in a similar way, we arrive at the following statements.
Statement 1. Least common multiple of coprime numbers a 1 , a 2 , a 3 ,...,a m is equal to their product a 1 · a 2 · a 3 ··· a m.
Statement 2. Any number that is divisible by each of the coprime numbers a 1 , a 2 , a 3 ,...,a m is also divisible by their product a 1 · a 2 · a 3 ··· a m.
The material presented below is a logical continuation of the theory from the article entitled LCM - least common multiple, definition, examples, relationship 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 connections between NOC 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.
Example.
Find the least common multiple of two numbers 126 and 70.
Solution.
In this example a=126 , b=70 . Let us 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 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: GCD(126, 70)=126·70:GCD(126, 70)= 126·70:14=630.
Answer:
LCM(126, 70)=630 .
Example.
What is LCM(68, 34) equal to?
Solution.
Because 68 is divisible by 34, then GCD(68, 34)=34. Now we calculate the least common multiple: GCD(68, 34)=68·34:GCD(68, 34)= 68·34:34=68.
Answer:
LCM(68, 34)=68 .
Note that the previous example fits the following rule for finding the LCM for positive integers a and b: if the number 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 section finding gcd by factoring 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 75 and 210, that is, NOC(75, 210)= 2·3·5·5·7=1,050.
Example.
Factor the numbers 441 and 700 into prime factors and find the least common multiple of these numbers.
Solution.
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.
Answer:
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).
Example.
Find the least common multiple of 84 and 648.
Solution.
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.
Answer:
LCM(84, 648)=4,536 .
Finding the LCM of three or more numbers
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.
Theorem.
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.
Example.
Find the LCM of four numbers 140, 9, 54 and 250.
Solution.
In this example, a 1 =140, a 2 =9, a 3 =54, a 4 =250.
First we find m 2 = LOC(a 1, a 2) = LOC(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 where GCD(140, 9)=140 9:GCD(140, 9)= 140·9:1=1,260. That is, m 2 =1 260.
Now we find m 3 = LOC (m 2 , a 3) = LOC (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.
All that remains is to find m 4 = LOC(m 3, a 4) = LOC(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, GCM(3,780, 250)=10, whence GCM(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.
Answer:
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.
Example.
Find the least common multiple of the five numbers 84, 6, 48, 7, 143.
Solution.
First, we obtain the decomposition of these numbers into prime factors: 84 = 2 2 3 7 , 6 = 2 3 , 48 = 2 2 2 2 3 , 7 (7 – 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.