Finding a common multiple of two numbers. Ways to find the least common multiple, nok is, and all explanations

Second number: b=

Digit separator No space separator " ´

Result:

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

Greatest natural number, by which the numbers a and b are divisible without a remainder, is called greatest common divisor(gcd) of these numbers. Denoted gcd(a,b), (a,b), gcd(a,b) or hcf(a,b).

Least common multiple(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).

Integers a and b are called coprime 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 a common divisor of these numbers, i.e. find such a number λ , which divides the numbers a 1 and a 2 at the same time. Let's describe the algorithm.

1) In this article, the word number will mean an integer.

Let a 1 ≥ a 2 and let

where m 1 , a 3 are some integers, a 3 <a 2 (remainder from division a 1 on a 2 should be less a 2).

Let's pretend that λ divides a 1 and a 2 , then λ divides m 1 a 2 and λ divides a 1 −m 1 a 2 =a 3 (Assertion 2 of the article "Divisibility of numbers. Sign of divisibility"). It follows that every common divisor a 1 and a 2 is a common divisor a 2 and a 3 . The converse 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 are also divided into λ . Hence 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 a common divisor of numbers a 1 and a 2 reduced to a simpler problem of finding a common divisor of numbers a 2 and a 3 .

If a 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 of division a 2 on a 3 (a 4 <a 3)). By similar reasoning, we come to the conclusion that the common divisors of numbers a 3 and a 4 is the same as 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 , ... numbers that are constantly decreasing, and since there is a finite number of integers between a 2 and 0, then at some step n, remainder of the division a n on a n+1 will be equal to zero ( a n+2=0).

Every common divisor λ numbers a 1 and a 2 is also a divisor of numbers a 2 and a 3 , a 3 and a 4 , .... a n and a n+1 . The converse is also true, common divisors of numbers a n and a n+1 are also divisors of numbers a n−1 and a n , .... , a 2 and a 3 , a 1 and a 2. But the common divisor 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 (recall that a n+2=0). Consequently a n+1 is also a divisor of numbers a 1 and a 2 .

Note that the number a n+1 is the greatest number divisor a n and a n+1 , since the greatest divisor a n+1 is itself a n+1 . If a 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 are called greatest common divisor numbers a 1 and a 2 .

Numbers a 1 and a 2 can be both positive and 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 not defined.

The above algorithm is called Euclid's 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.

At 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 numbers a 1 and a 2 is equal to one. Then these numbers are called coprime numbers that do not have a common divisor.

Theorem 1. If a a 1 and a 2 relatively prime 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 Euclid's algorithm for finding the greatest common divisor of numbers a 1 and a 2 (see above).

It follows from the conditions of the theorem that the greatest common divisor of numbers a 1 and a 2 , and therefore a n and a n+1 is 1. I.e. a n+1=1.

Let's multiply all these equalities by λ , then

Let the common divisor a 1 λ and a 2 is δ . Then δ enters as a factor in a 1 λ , m 1 a 2 λ and in a 1 λ -m 1 a 2 λ =a 3 λ (See "Divisibility of numbers", Statement 2). Further δ enters as a factor in a 2 λ and m 2 a 3 λ , and hence enters as a factor in a 2 λ -m 2 a 3 λ =a 4 λ .

By reasoning in this way, we are convinced that δ enters as a factor 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 δ enters as a factor in λ . Hence the number δ is a common divisor of numbers λ and a 2 .

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 coprime, i.e. have a single common divisor 1. Then ac and b also have a single common divisor 1. Hence 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 assertion condition ak and b have a common divisor b. By virtue of Theorem 1, b must be a common divisor b and k. Consequently 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 we have two rows of numbers

such that every number in the first row is prime with respect to every number in the second row. Then the product

It is required to find such numbers that are divisible by each of these numbers.

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

where s 1 is some integer. Then

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

a 1 and a 2 coprime, then the least common multiple of the numbers a 1 and a 2:

Find the least common multiple of these numbers.

It follows from the above that any multiple of the numbers a 1 , a 2 , a 3 must be a multiple of numbers ε and a 3 and vice versa. Let the least common multiple of the numbers ε and a 3 is ε one . Further, a multiple of numbers a 1 , a 2 , a 3 , a 4 must be a multiple of numbers ε 1 and a four . Let the least common multiple of the numbers ε 1 and a 4 is ε 2. Thus, we found out that all multiples of numbers a 1 , a 2 , a 3 ,...,a m coincide with multiples of some specific number ε n , which is called the least common multiple of the given numbers.

In the particular case when the numbers a 1 , a 2 , a 3 ,...,a m coprime, then the least common multiple of the numbers a 1 , a 2 as shown above has the form (3). Further, since a 3 prime with respect to numbers a 1 , a 2 , then a 3 is a prime relative number a one · a 2 (Corollary 1). So the least common multiple of the numbers a 1 ,a 2 ,a 3 is a number a one · a 2 · a 3 . Arguing in a similar way, we arrive at the following assertions.

Statement 1. Least common multiple of coprime numbers a 1 , a 2 , a 3 ,...,a m is equal to their product a one · 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 one · a 2 · a 3 ··· a m .

Definition. The largest natural number by which the numbers a and b are divisible without a remainder is called greatest common divisor (gcd) these numbers.

Let's find the greatest common divisor of the numbers 24 and 35.
The divisors of 24 will be the numbers 1, 2, 3, 4, 6, 8, 12, 24, and the divisors of 35 will be the numbers 1, 5, 7, 35.
We see that the numbers 24 and 35 have only one common divisor - the number 1. Such numbers are called coprime.

Definition. The natural numbers are called coprime if their greatest common divisor (gcd) is 1.

Greatest Common Divisor (GCD) can be found without writing out all the divisors of the given numbers.

Factoring the numbers 48 and 36, we get:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
From the factors included in the expansion of the first of these numbers, we delete those that are not included in the expansion of the second number (i.e., two deuces).
The factors 2 * 2 * 3 remain. Their product is 12. This number is the greatest common divisor of the numbers 48 and 36. The greatest common divisor of three or more numbers is also found.

To find greatest common divisor

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.

If all given numbers are divisible by one of them, then this number is greatest common divisor given numbers.
For example, the greatest common divisor of 15, 45, 75, and 180 is 15, since it divides all other numbers: 45, 75, and 180.

Least common multiple (LCM)

Definition. Least common multiple (LCM) natural numbers a and b are the smallest natural number that is a multiple of both a and b. The least common multiple (LCM) of the numbers 75 and 60 can be found without writing out multiples of these numbers in a row. To do this, we decompose 75 and 60 into simple factors: 75 \u003d 3 * 5 * 5, and 60 \u003d 2 * 2 * 3 * 5.
We write out the factors included in the expansion of the first of these numbers, and add to them the missing factors 2 and 2 from the expansion of the second number (that is, we combine the factors).
We get five factors 2 * 2 * 3 * 5 * 5, the product of which is 300. This number is the least common multiple of the numbers 75 and 60.

Also find the least common multiple of three or more numbers.

To find the least common multiple several natural numbers, you need:
1) decompose them into prime factors;
2) write out 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.

Note that if one of these numbers is divisible by all other numbers, then this number is the least common multiple of these numbers.
For example, the least common multiple of 12, 15, 20, and 60 would be 60, since it is divisible by all given numbers.

Pythagoras (VI century BC) and his students studied the issue of divisibility of numbers. A number equal to the sum of all its divisors (without the number itself), they called the perfect number. For example, the numbers 6 (6 = 1 + 2 + 3), 28 (28 = 1 + 2 + 4 + 7 + 14) are perfect. The next perfect numbers are 496, 8128, 33,550,336. The Pythagoreans knew only the first three perfect numbers. The fourth - 8128 - became known in the 1st century. n. e. The fifth - 33 550 336 - was found in the 15th century. By 1983, 27 perfect numbers were already known. But until now, scientists do not know whether there are odd perfect numbers, whether there is the largest perfect number.
The interest of ancient mathematicians in prime numbers is due to the fact that any number is either prime or can be represented as a product of prime numbers, that is, prime numbers are like bricks from which the rest of the natural numbers are built.
You probably noticed that prime numbers in the series of natural numbers occur unevenly - in some parts of the series there are more of them, in others - less. But the further we move along the number series, the rarer the prime numbers. The question arises: does the last (largest) prime number exist? The ancient Greek mathematician Euclid (3rd century BC), in his book “Beginnings”, which for two thousand years was the main textbook of mathematics, proved that there are infinitely many prime numbers, that is, behind each prime number there is an even greater prime number.
To find prime numbers, another Greek mathematician of the same time, Eratosthenes, came up with such a method. He wrote down all the numbers from 1 to some number, and then crossed out the unit, which is neither a prime nor a composite number, then crossed out through one all the numbers after 2 (numbers that are multiples of 2, i.e. 4, 6 , 8, etc.). The first remaining number after 2 was 3. Then, after two, all the numbers after 3 were crossed out (numbers that are multiples of 3, i.e. 6, 9, 12, etc.). in the end, only the prime numbers remained uncrossed out.

Common multiples

Simply put, any integer that is divisible by each of the given numbers is common multiple given integers.

You can find the common multiple of two or more integers.

Example 1

Calculate the common multiple of two numbers: $2$ and $5$.

Solution.

By definition, the common multiple of $2$ and $5$ is $10$, because it is a multiple of $2$ and $5$:

The common multiples of the numbers $2$ and $5$ will also be the numbers $–10, 20, –20, 30, –30$, etc., because they are all divisible by $2$ and $5$.

Remark 1

Zero is a common multiple of any number of non-zero integers.

According to the properties of divisibility, if a certain number is a common multiple of several numbers, then the number opposite in sign will also be a common multiple of the given numbers. This can be seen from the considered example.

For given integers, you can always find their common multiple.

Example 2

Calculate the common multiple of $111$ and $55$.

Solution.

Multiply the given numbers: $111\div 55=6105$. It is easy to check that the number $6105$ is divisible by the number $111$ and the number $55$:

$6105\div 111=55$;

$6105\div 55=111$.

Thus, $6105$ is a common multiple of $111$ and $55$.

Answer: the common multiple of $111$ and $55$ is $6105$.

But, as we have already seen from the previous example, this common multiple is not one. Other common multiples would be $-6105, 12210, -12210, 61050, -61050$, and so on. Thus, we have come to the following conclusion:

Remark 2

Any set of integers has an infinite number of common multiples.

In practice, they are limited to finding common multiples of only positive integer (natural) numbers, because the sets of multiples of a given number and its opposite coincide.

Finding the Least Common Multiple

Most often, of all multiples of a given number, the least common multiple (LCM) is used.

Definition 2

The least positive common multiple of the given integers is least common multiple these numbers.

Example 3

Calculate the LCM of the numbers $4$ and $7$.

Solution.

Because these numbers have no common divisors, then $LCM(4,7)=28$.

Answer: $LCM(4,7)=28$.

Finding the NOC through the NOD

Because there is a connection between LCM and GCD, with its help it is possible to calculate LCM of two positive integers:

Remark 3

Example 4

Calculate the LCM of the numbers $232$ and $84$.

Solution.

Let's use the formula for finding the LCM through the GCD:

$LCD (a,b)=\frac(a\cdot b)(gcd (a,b))$

Let's find the gcd of the numbers $232$ and $84$ using the Euclidean algorithm:

$232=84\cdot 2+64$,

$84=64\cdot 1+20$,

$64=20\cdot 3+4$,

Those. $gcd (232, 84)=4$.

Let's find $LCM (232, 84)$:

$LCC(232,84)=\frac(232\cdot 84)(4)=58\cdot 84=4872$

Answer: $NOK(232.84)=4872$.

Example 5

Calculate $LCM (23, 46)$.

Solution.

Because $46$ is evenly divisible by $23$, then $gcd(23, 46)=23$. Let's find the NOC:

$LCC(23,46)=\frac(23\cdot 46)(23)=46$

Answer: $NOK(23.46)=46$.

Thus, one can formulate rule:

Remark 4

The material presented below is a logical continuation of the theory from the article under the heading LCM - least common multiple, definition, examples, relationship between LCM and GCD. Here we will talk about finding the least common multiple (LCM), and pay special attention to solving examples. Let us first show how the LCM of two numbers is calculated in terms of the GCD of these numbers. Next, consider finding the least common multiple by factoring numbers into prime factors. After that, we will focus on finding the LCM of three or more numbers, and also pay attention to the calculation of the LCM of negative numbers.

Page navigation.

Calculation of the least common multiple (LCM) through gcd

One way to find the least common multiple is based on the relationship between LCM and GCD. The existing relationship between LCM and GCD allows you to calculate the least common multiple of two positive integers through the known greatest common divisor. The corresponding formula has the form LCM(a, b)=a b: GCM(a, b) . Consider examples of finding the LCM according to the above formula.

Example.

Find the least common multiple of the two numbers 126 and 70 .

Solution.

In this example a=126 , b=70 . Let us use the relationship between LCM and GCD expressed by the formula LCM(a, b)=a b: GCM(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 according to the written formula.

Find gcd(126, 70) using Euclid's algorithm: 126=70 1+56 , 70=56 1+14 , 56=14 4 , hence gcd(126, 70)=14 .

Now we find the required least common multiple: LCM(126, 70)=126 70: GCM(126, 70)= 126 70:14=630 .

Answer:

LCM(126, 70)=630 .

Example.

What is LCM(68, 34) ?

Solution.

Because 68 is evenly divisible by 34 , then gcd(68, 34)=34 . Now we calculate the least common multiple: LCM(68, 34)=68 34: LCM(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 we make a product of all prime factors of these numbers, after which we exclude from this product all common prime factors that are present in the expansions of these numbers, then the resulting product will be equal to the least common multiple of these numbers.

The announced rule for finding the LCM follows from the equality LCM(a, b)=a b: GCM(a, b). Indeed, the product of the numbers a and b is equal to the product of all the factors involved in the expansions of the numbers a and b. In turn, gcd(a, b) is equal to the product of all prime factors that are simultaneously present in the expansions of the numbers a and b (which is described in the section on finding the gcd using the decomposition of numbers into prime factors).

Let's take an example. Let we know that 75=3 5 5 and 210=2 3 5 7 . Compose the product of all factors of these expansions: 2 3 3 5 5 5 7 . Now we exclude from this product all the factors that are present both in the expansion of the number 75 and in the expansion of the number 210 (such 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=1 050.

Example.

After factoring the numbers 441 and 700 into prime factors, find the least common multiple of these numbers.

Solution.

Let's decompose 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 make a product of all the factors involved in the expansions of these numbers: 2 2 3 3 5 5 7 7 7 . Let us exclude from this product all the 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 . In this way, LCM(441, 700)=2 2 3 3 5 5 7 7=44 100.

Answer:

LCM(441, 700)= 44 100 .

The rule for finding the LCM using the decomposition of numbers into prime factors can be formulated a little differently. If we add the missing factors from the expansion of the number b 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 all the same numbers 75 and 210, their expansions 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 decomposition of the number 75, we add the missing factors 2 and 7 from the decomposition of the number 210, we get the product 2 3 5 5 7 , the value of which is LCM(75, 210) .

Example.

Find the least common multiple of 84 and 648.

Solution.

We first obtain the decomposition 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 decomposition of the number 84 we add the missing factors 2 , 3 , 3 and 3 from the decomposition of the number 648 , we get the product 2 2 2 3 3 3 3 7 , which is equal to 4 536 . Thus, the desired least common multiple of the numbers 84 and 648 is 4,536.

Answer:

LCM(84, 648)=4 536 .

Finding the LCM of three or more numbers

The least common multiple of three or more numbers can be found by successively finding the LCM of two numbers. Recall the corresponding theorem, which gives a way to find the LCM of three or more numbers.

Theorem.

Let positive integers a 1 , a 2 , …, a k be given, the least common multiple m k of these numbers is found in the sequential calculation m 2 = LCM (a 1 , a 2) , m 3 = LCM (m 2 , a 3) , … , m k =LCM(m k−1 , a k) .

Consider the application of this theorem on the example of finding the least common multiple of four numbers.

Example.

Find the LCM of the 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 \u003d LCM (a 1, a 2) \u003d 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 , whence LCM(140, 9)=140 9: LCM(140, 9)= 140 9:1=1 260 . That is, m 2 =1 260 .

Now we find m 3 \u003d LCM (m 2, a 3) \u003d LCM (1 260, 54). Let's calculate it through gcd(1 260, 54) , which is also determined by the Euclid algorithm: 1 260=54 23+18 , 54=18 3 . Then gcd(1 260, 54)=18 , whence LCM(1 260, 54)= 1 260 54:gcd(1 260, 54)= 1 260 54:18=3 780 . That is, m 3 \u003d 3 780.

Left to find m 4 \u003d LCM (m 3, a 4) \u003d LCM (3 780, 250). To do this, we find GCD(3 780, 250) using the Euclid algorithm: 3 780=250 15+30 , 250=30 8+10 , 30=10 3 . Therefore, gcd(3 780, 250)=10 , whence gcd(3 780, 250)= 3 780 250:gcd(3 780, 250)= 3 780 250:10=94 500 . That is, m 4 \u003d 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, the least common multiple of three or more numbers is conveniently found using prime factorizations of given numbers. In this case, the following rule should be followed. 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 obtained factors, and so on.

Consider an example of finding the least common multiple using the decomposition of numbers into prime factors.

Example.

Find the least common multiple of five numbers 84 , 6 , 48 , 7 , 143 .

Solution.

First, we obtain the expansions of these numbers into prime factors: 84=2 2 3 7 , 6=2 3 , 48=2 2 2 2 3 , 7 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 expansion of the number 6 does not contain missing factors, since both 2 and 3 are already present in the expansion of the first number 84 . Further 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 is no need to add factors 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 .

Greatest Common Divisor

Definition 2

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

Let $a$ and $b$ be natural numbers. The number $c$ is called a common divisor for both $a$ and $b$.

The set of common divisors of the numbers $a$ and $b$ is finite, since none of these divisors can be greater than $a$. This means that among these divisors there is the largest one, which is called the greatest common divisor of the numbers $a$ and $b$, and the notation is used to denote it:

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

To find the greatest common divisor of two numbers:

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

Example 1

Find the gcd of the numbers $121$ and $132.$

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Choose the numbers that are included in the expansion of these numbers

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

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

$gcd=2\cdot 11=22$

Example 2

Find the GCD of monomials $63$ and $81$.

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

Let's decompose numbers into prime factors

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

We select the numbers that are included in the expansion of these numbers

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Let's find the product of the numbers found in step 2. The resulting number will be the desired greatest common divisor.

$gcd=3\cdot 3=9$

You can find the GCD of two numbers in another way, using the set of divisors of numbers.

Example 3

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

Solution:

Find the set of divisors of $48$: $\left$(\rm 1,2,3.4.6,8,12,16,24,48)\right$$

Now let's find the set of divisors of $60$:$\ \left$(\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right$$

Let's find the intersection of these sets: $\left$(\rm 1,2,3,4,6,12)\right$$ - this set will determine the set of common divisors of the numbers $48$ and $60$. The largest element in this set will be the number $12$. So the greatest common divisor of $48$ and $60$ is $12$.

Definition of NOC

Definition 3

common multiple of natural numbers$a$ and $b$ is a natural number that is a multiple of both $a$ and $b$.

Common multiples of numbers are numbers that are divisible by the original without a remainder. For example, for the numbers $25$ and $50$, the common multiples will be the numbers $50,100,150,200$, etc.

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

To find the LCM of two numbers, you need:

Decompose numbers into prime factors
Write out the factors that are part of the first number and add to them the factors that are part of the second and do not go to the first

Example 4

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

We will find according to the presented algorithm. For this

Decompose numbers into prime factors

$99=3\cdot 3\cdot 11$

Write down the factors included in the first

add to them factors that are part of the second and do not go to the first

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

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

Compiling lists of divisors of numbers is often very time consuming. There is a way to find GCD called Euclid's algorithm.

Statements on which Euclid's algorithm is based:

If $a$ and $b$ are natural numbers, and $a\vdots b$, then $D(a;b)=b$

If $a$ and $b$ are natural numbers such that $b

Using $D(a;b)= D(a-b;b)$, we can successively decrease the numbers under consideration until we reach a pair of numbers such that one of them is divisible by the other. Then the smaller of these numbers will be the desired greatest common divisor for the numbers $a$ and $b$.

Properties of GCD and LCM

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

If K$(a;b)=k$ and $m$-natural number, then K$(am;bm)=km$

If $d$ is a common divisor for $a$ and $b$, then K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d) $

If $a\vdots c$ and $b\vdots c$ , then $\frac(ab)(c)$ is a common multiple of $a$ and $b$

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

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

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