The greatest common divisor and the least common multiple are key arithmetic concepts that allow you to easily operate with ordinary fractions. LCM and are most often used to find the common denominator of several fractions.

Basic concepts

The divisor of an integer X is another integer Y by which X is divisible without a remainder. For example, the divisor of 4 is 2, and 36 is 4, 6, 9. A multiple of the integer X is a number Y that is divisible by X without a remainder. For example, 3 is a multiple of 15, and 6 is a multiple of 12.

For any pair of numbers, we can find their common divisors and multiples. For example, for 6 and 9, the common multiple is 18, and the common divisor is 3. Obviously, pairs can have several divisors and multiples, so the largest divisor of the GCD and the smallest multiple of the LCM are used in the calculations.

The smallest divisor does not make sense, since for any number it is always one. The largest multiple is also meaningless, since the sequence of multiples tends to infinity.

Finding GCD

There are many methods for finding the greatest common divisor, the most famous of which are:

• sequential enumeration of divisors, selection of common ones for a pair and search for the largest of them;
• decomposition of numbers into indivisible factors;
• Euclid's algorithm;
• binary algorithm.

Today, in educational institutions, the most popular methods of decomposition into prime factors and the Euclidean algorithm. The latter, in turn, is used in solving Diophantine equations: the search for GCD is required to check the equation for the possibility of resolving it in integers.

Finding the NOC

The least common multiple is also exactly determined by iterative enumeration or factorization into indivisible factors. In addition, it is easy to find the LCM if the largest divisor has already been determined. For numbers X and Y, LCM and GCD are related by the following relation:

LCM(X,Y) = X × Y / GCM(X,Y).

For example, if gcd(15,18) = 3, then LCM(15,18) = 15 × 18 / 3 = 90. The most obvious use of LCM is to find the common denominator, which is the least common multiple of the given fractions.

Coprime numbers

If a pair of numbers has no common divisors, then such a pair is called coprime. The GCM for such pairs is always equal to one, and based on the connection of divisors and multiples, the GCM for coprime is equal to their product. For example, the numbers 25 and 28 are coprime, because they have no common divisors, and LCM(25, 28) = 700, which corresponds to their product. Any two indivisible numbers will always be coprime.

Common Divisor and Multiple Calculator

With our calculator you can calculate the GCD and LCM for an arbitrary number of numbers to choose from. Tasks for calculating common divisors and multiples are found in arithmetic of grades 5 and 6, however, GCD and LCM are the key concepts of mathematics and are used in number theory, planimetry and communicative algebra.

Real life examples

Common denominator of fractions

The least common multiple is used when finding the common denominator of several fractions. Suppose in an arithmetic problem it is required to sum 5 fractions:

1/8 + 1/9 + 1/12 + 1/15 + 1/18.

To add fractions, the expression must be reduced to a common denominator, which reduces to the problem of finding the LCM. To do this, select 5 numbers in the calculator and enter the denominator values ​​in the appropriate cells. The program will calculate LCM (8, 9, 12, 15, 18) = 360. Now you need to calculate additional factors for each fraction, which are defined as the ratio of LCM to the denominator. So the extra multipliers would look like:

• 360/8 = 45
• 360/9 = 40
• 360/12 = 30
• 360/15 = 24
• 360/18 = 20.

After that, we multiply all the fractions by the corresponding additional factor and get:

45/360 + 40/360 + 30/360 + 24/360 + 20/360.

We can easily add such fractions and get the result in the form of 159/360. We reduce the fraction by 3 and see the final answer - 53/120.

Solution of linear Diophantine equations

Linear Diophantine equations are expressions of the form ax + by = d. If the ratio d / gcd(a, b) is an integer, then the equation is solvable in integers. Let's check a couple of equations for the possibility of an integer solution. First, check the equation 150x + 8y = 37. Using a calculator, we find gcd (150.8) = 2. Divide 37/2 = 18.5. The number is not an integer, therefore, the equation does not have integer roots.

Let's check the equation 1320x + 1760y = 10120. Use a calculator to find gcd(1320, 1760) = 440. Divide 10120/440 = 23. As a result, we get an integer, therefore, the Diophantine equation is solvable in integer coefficients.

Conclusion

GCD and LCM play an important role in number theory, and the concepts themselves are widely used in various areas of mathematics. Use our calculator to calculate the largest divisors and smallest multiples of any number of numbers.

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.
Let's 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.

Mathematical expressions and tasks require a lot of additional knowledge. NOC is one of the main ones, especially often used in the topic. The topic is studied in high school, while it is not particularly difficult to understand material, it will not be difficult for a person familiar with powers and the multiplication table to select the necessary numbers and find the result.

Definition

A common multiple is a number that can be completely divided into two numbers at the same time (a and b). Most often, this number is obtained by multiplying the original numbers a and b. The number must be divisible by both numbers at once, without deviations.

NOC is a short name, which is taken from the first letters.

Ways to get a number

To find the LCM, the method of multiplying numbers is not always suitable, it is much better suited for simple one-digit or two-digit numbers. It is customary to divide into factors, the larger the number, the more factors there will be.

Example #1

For the simplest example, schools usually take simple, one-digit or two-digit numbers. For example, you need to solve the following task, find the least common multiple of the numbers 7 and 3, the solution is quite simple, just multiply them. As a result, there is the number 21, there is simply no smaller number.

Example #2

The second option is much more difficult. The numbers 300 and 1260 are given, finding the LCM is mandatory. To solve the task, the following actions are assumed:

Decomposition of the first and second numbers into the simplest factors. 300 = 2 2 * 3 * 5 2 ; 1260 = 2 2 * 3 2 * 5 * 7. The first stage has been completed.

The second stage involves working with the already obtained data. Each of the received numbers must participate in the calculation of the final result. For each factor, the largest number of occurrences is taken from the original numbers. LCM is a common number, so the factors from the numbers must be repeated in it to the last, even those that are present in one copy. Both initial numbers have in their composition the numbers 2, 3 and 5, in different degrees, 7 is only in one case.

To calculate the final result, you need to take each number in the largest of their represented powers, into the equation. It remains only to multiply and get the answer, with the correct filling, the task fits into two steps without explanation:

1) 300 = 2 2 * 3 * 5 2 ; 1260 = 2 2 * 3 2 *5 *7.

2) NOK = 6300.

That's the whole task, if you try to calculate the desired number by multiplying, then the answer will definitely not be correct, since 300 * 1260 = 378,000.

Examination:

6300 / 300 = 21 - true;

6300 / 1260 = 5 is correct.

The correctness of the result is determined by checking - dividing the LCM by both original numbers, if the number is an integer in both cases, then the answer is correct.

What does NOC mean in mathematics

As you know, there is not a single useless function in mathematics, this one is no exception. The most common purpose of this number is to bring fractions to a common denominator. What is usually studied in grades 5-6 of high school. It is also additionally a common divisor for all multiples, if such conditions are in the problem. Such an expression can find a multiple not only of two numbers, but also of a much larger number - three, five, and so on. The more numbers - the more actions in the task, but the complexity of this does not increase.

For example, given the numbers 250, 600 and 1500, you need to find their total LCM:

1) 250 = 25 * 10 = 5 2 * 5 * 2 = 5 3 * 2 - this example describes the factorization in detail, without reduction.

2) 600 = 60 * 10 = 3 * 2 3 *5 2 ;

3) 1500 = 15 * 100 = 33 * 5 3 *2 2 ;

In order to compose an expression, it is required to mention all factors, in this case 2, 5, 3 are given - for all these numbers it is required to determine the maximum degree.

Attention: all multipliers must be brought to full simplification, if possible, decomposing to the level of single digits.

Examination:

1) 3000 / 250 = 12 - true;

2) 3000 / 600 = 5 - true;

3) 3000 / 1500 = 2 is correct.

This method does not require any tricks or genius level abilities, everything is simple and clear.

Another way

In mathematics, a lot is connected, a lot can be solved in two or more ways, the same goes for finding the least common multiple, LCM. The following method can be used in the case of simple two-digit and single-digit numbers. A table is compiled in which the multiplier is entered vertically, the multiplier horizontally, and the product is indicated in the intersecting cells of the column. You can reflect the table by means of a line, a number is taken and the results of multiplying this number by integers are written in a row, from 1 to infinity, sometimes 3-5 points are enough, the second and subsequent numbers are subjected to the same computational process. Everything happens until a common multiple is found.

Given the numbers 30, 35, 42, you need to find the LCM that connects all the numbers:

1) Multiples of 30: 60, 90, 120, 150, 180, 210, 250, etc.

2) Multiples of 35: 70, 105, 140, 175, 210, 245, etc.

3) Multiples of 42: 84, 126, 168, 210, 252, etc.

It is noticeable that all the numbers are quite different, the only common number among them is 210, so it will be the LCM. Among the processes associated with this calculation, there is also the greatest common divisor, which is calculated according to similar principles and is often encountered in neighboring problems. The difference is small, but significant enough, LCM involves the calculation of a number that is divisible by all given initial values, and GCD assumes the calculation of the largest value by which the initial numbers are divided.

Greatest Common Divisor

Definition 2

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

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

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

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

To find the greatest common divisor of two numbers:

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

Example 1

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

$242=2\cdot 11\cdot 11$

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

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

$242=2\cdot 11\cdot 11$

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

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

$gcd=2\cdot 11=22$

Example 2

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

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

Let's decompose numbers into prime factors

$63=3\cdot 3\cdot 7$

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

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

$63=3\cdot 3\cdot 7$

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

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

$gcd=3\cdot 3=9$

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

Example 3

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

Solution:

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

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

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

Definition of NOC

Definition 3

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

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

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

To find the LCM of two numbers, you need:

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

Example 4

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

We will find according to the presented algorithm. For this

Decompose numbers into prime factors

$99=3\cdot 3\cdot 11$

Write down the factors included in the first

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

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

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

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

Statements on which Euclid's algorithm is based:

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

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

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

Properties of GCD and LCM

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

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

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

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

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

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

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

The least common multiple of two numbers is directly related to the greatest common divisor of those numbers. This link between GCD and NOC is defined by the following theorem.

Theorem.

The least common multiple of two positive integers a and b is equal to the product of a and b divided by the greatest common divisor of a and b, that is, LCM(a, b)=a b: GCD(a, b).

Proof.

Let M is some multiple of the numbers a and b. That is, M is divisible by a, and by the definition of divisibility, there is some integer k such that the equality M=a·k is true. But M is also divisible by b, then a k is divisible by b.

Denote gcd(a, b) as d . Then we can write down the equalities a=a 1 ·d and b=b 1 ·d, and a 1 =a:d and b 1 =b:d will be coprime numbers. Therefore, the condition obtained in the previous paragraph that a k is divisible by b can be reformulated as follows: a 1 d k is divisible by b 1 d , and this, due to the properties of divisibility, is equivalent to the condition that a 1 k is divisible by b one .

We also need to write down two important corollaries from the considered theorem.

Common multiples of two numbers are the same as multiples of their least common multiple.

This is true, since any common multiple of M numbers a and b is defined by the equality M=LCM(a, b) t for some integer value t .

The least common multiple of coprime positive numbers a and b is equal to their product.

The rationale for this fact is quite obvious. Since a and b are coprime, then gcd(a, b)=1 , therefore, LCM(a, b)=a b: GCD(a, b)=a b:1=a b.

Least common multiple of three or more numbers

Finding the least common multiple of three or more numbers can be reduced to successively finding the LCM of two numbers. How this is done is indicated in the following theorem. a 1 , a 2 , …, a k coincide with common multiples of numbers m k-1 and a k , therefore, coincide with multiples of m k . And since the least positive multiple of the number m k is the number m k itself, then the least common multiple of the numbers a 1 , a 2 , …, a k is m k .

Bibliography.

• Vilenkin N.Ya. etc. Mathematics. Grade 6: textbook for educational institutions.
• Vinogradov I.M. Fundamentals of number theory.
• Mikhelovich Sh.Kh. Number theory.
• Kulikov L.Ya. and others. Collection of problems in algebra and number theory: Textbook for students of fiz.-mat. specialties of pedagogical institutes.