Finding the least common divisor. Finding the least common multiple, methods, examples of finding the LCM

Greatest common divisor and least common multiple are key arithmetic concepts that allow you to operate effortlessly 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 divided without leaving a remainder. For example, the divisor of 4 is 2, and 36 is 4, 6, 9. A multiple of an 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 when calculating, use greatest divisor GCD and least multiple of LCM.

The least divisor is meaningless, since for any number it is always one. The greatest multiple is also meaningless, since the sequence of multiples goes to infinity.

Finding gcd

To find the largest common divisor There are many methods, the most famous of which are:

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

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

Finding the NOC

The least common multiple is also determined by sequential search or decomposition into indivisible factors. In addition, it is easy to find the LCM if the greatest divisor has already been determined. For numbers X and Y, the LCM and GCD are related by the following relationship:

LCD(X,Y) = X × Y / GCD(X,Y).

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

Coprime numbers

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

Common divisor and multiple calculator

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

Real life examples

Common denominator of fractions

Least common multiple is used when finding the common denominator of multiple fractions. Let in arithmetic problem you need to sum 5 fractions:

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

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

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

After this, we multiply all the fractions by the corresponding additional multiplier and we get:

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

We can easily sum such fractions and get the result as 159/360. We reduce the fraction by 3 and see the final answer - 53/120.

Solving 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 to see if they have an integer solution. First, let's 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 a big role in number theory, and the concepts themselves are widely used in a wide variety of areas of mathematics. Use our calculator to calculate the greatest divisors and least multiples of any number of numbers.

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

Theorem.

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

Proof.

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

Let's denote gcd(a, b) as d. Then we can write the equalities a=a 1 ·d and b=b 1 ·d, and a 1 =a:d and b 1 =b:d will be relatively prime numbers. Consequently, the condition obtained in the previous paragraph that a · k is divisible by b can be reformulated as follows: a 1 · d · k is divided by b 1 · d , and this, due to divisibility properties, is equivalent to the condition that a 1 · k is divisible by b 1 .

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

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

This is indeed the case, since any common multiple of M of the numbers a and b is determined by the equality M=LMK(a, b)·t for some integer value t.

Least common multiple of coprime positive numbers a and b are equal to their product.

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

Least common multiple of three or more numbers

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

Bibliography.

• Vilenkin N.Ya. and others. Mathematics. 6th grade: textbook for general education institutions.
• Vinogradov I.M. Fundamentals of number theory.
• Mikhelovich Sh.H. Number theory.
• Kulikov L.Ya. and others. Collection of problems in algebra and number theory: Tutorial for students of physics and mathematics. specialties of pedagogical institutes.

Finding the greatest common divisor of three or more numbers can be reduced to sequentially finding the gcd of two numbers. We mentioned this when studying the properties of GCD. There we formulated and proved the theorem: the greatest common divisor of several numbers a 1 , a 2 , …, a k equal to the number dk, which is found by sequential calculation 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.

Let's see what the process of finding the gcd of several numbers looks like by looking at the solution to the example.

Example.

Find the greatest common divisor of four numbers 78 , 294 , 570 And 36 .

Solution.

In this example a 1 =78, a 2 =294, a 3 =570, a 4 =36.

First, using the Euclidean algorithm, we determine the greatest common divisor d 2 first two numbers 78 And 294 . When dividing we get the equalities 294=78 3+60; 78=60 1+18;60=18·3+6 And 18=6·3. Thus, d 2 =GCD(78, 294)=6.

Now let's calculate d 3 =GCD(d 2, a 3)=GCD(6, 570). Let's use the Euclidean algorithm again: 570=6·95, hence, d 3 =GCD(6, 570)=6.

It remains to calculate d 4 =GCD(d 3, a 4)=GCD(6, 36). Because 36 divided by 6 , That d 4 =GCD(6, 36)=6.

Thus, the greatest common divisor of the four given numbers is equal to d 4 =6, that is, GCD(78, 294, 570, 36)=6.

Answer:

GCD(78, 294, 570, 36)=6.

Factoring numbers into prime factors also allows you to calculate the gcd of three or more numbers. In this case, the greatest common divisor is found as the product of all common prime factors of the given numbers.

Example.

Calculate the gcd of the numbers from the previous example using their prime factorizations.

Solution.

Let's break down the numbers 78 , 294 , 570 And 36 by prime factors, we get 78=2·3·13,294=2·3·7·7, 570=2 3 5 19, 36=2·2·3·3. The common prime factors of all given four numbers are the numbers 2 And 3 . Hence, GCD(78, 294, 570, 36)=2·3=6.

Answer:

GCD(78, 294, 570, 36)=6.

Top of page

Finding GCD of Negative Numbers

If one, several, or all of the numbers whose greatest divisor is to be found are negative numbers, then their gcd is equal to the greatest common divisor of the moduli of these numbers. This is due to the fact that opposite numbers a And −a have the same divisors, as we discussed when studying the properties of divisibility.

Example.

Find the gcd of negative integers −231 And −140 .

Solution.

The absolute value of a number −231 equals 231 , and the modulus of the number −140 equals 140 , And GCD(−231, −140)=GCD(231, 140). The Euclidean algorithm gives us the following equalities: 231=140 1+91; 140=91 1+49; 91=49 1+42; 49=42 1+7 And 42=7 6. Hence, GCD(231, 140)=7. Then the desired greatest common divisor of negative numbers is −231 And −140 equals 7 .

Answer:

GCD(−231, −140)=7.

Example.

Determine the gcd of three numbers −585 , 81 And −189 .

Solution.

When finding the greatest common divisor negative numbers you can replace them absolute values, that is, GCD(−585, 81, −189)=GCD(585, 81, 189). Number expansions 585 , 81 And 189 into prime factors have the form 585=3·3·5·13, 81=3·3·3·3 And 189=3·3·3·7. The common prime factors of these three numbers are 3 And 3 . Then GCD(585, 81, 189)=3·3=9, hence, GCD(−585, 81, −189)=9.

Answer:

GCD(−585, 81, −189)=9.

35. Roots of a polynomial. Bezout's theorem. (33 and above)

36. Multiple roots, criterion for multiplicity of roots.

Key words of the summary:Integers. Arithmetic operations on natural numbers. Divisibility of natural numbers. Simple and composite numbers. Factoring a natural number into prime factors. Divisibility signs by 2, 3, 5, 9, 4, 25, 10, 11. Greatest common divisor (GCD), as well as least common multiple (LCD). Division with remainder.

Integers- these are numbers that are used to count objects - 1, 2, 3, 4 , ... But the number 0 is not natural!

The set of natural numbers is denoted by N. Record "3 ∈ N" means that the number three belongs to the set of natural numbers, and the notation "0 ∉ N" means that the number zero does not belong to this set.

Decimal number system- positional radix number system 10 .

Arithmetic operations on natural numbers

For natural numbers the following actions are defined: addition, subtraction, multiplication, division, exponentiation, root extraction. The first four actions are arithmetic.

Let a, b and c be natural numbers, then

1. ADDITION. Term + Term = Sum

Properties of addition
1. Communicative a + b = b + a.
2. Conjunctive a + (b + c) = (a + b) + c.
3. a + 0= 0 + a = a.

2. SUBTRACT. Minuend - Subtrahend = Difference

Properties of Subtraction
1. Subtracting the sum from the number a - (b + c) = a - b - c.
2. Subtracting a number from the sum (a + b) - c = a + (b - c); (a + b) - c = (a - c) + b.
3. a - 0 = a.
4. a - a = 0.

3. MULTIPLICATION. Multiplier * Multiplier = Product

Properties of Multiplication
1. Communicative a*b = b*a.
2. Conjunctive a*(b*c) = (a*b)*c.
3. 1 * a = a * 1 = a.
4. 0 * a = a * 0 = 0.
5. Distributive (a + b) * c = ac + bc; (a - b) * c = ac - bc.

4. DIVISION. Dividend: Divisor = Quotient

Properties of division
1. a: 1 = a.
2. a: a = 1. You can't divide by zero!
3. 0: a= 0.

Procedure

1. First of all, the actions in parentheses.
2. Then multiplication, division.
3. And only at the end addition and subtraction.

Divisibility of natural numbers. Prime and composite numbers.

Divisor of a natural number A is the natural number to which A divided without remainder. Number 1 is a divisor of any natural number.

The natural number is called simple, if it only has two divisor: one and the number itself. For example, the numbers 2, 3, 11, 23 are prime numbers.

A number that has more than two divisors is called composite. For example, the numbers 4, 8, 15, 27 are composite numbers.

Divisibility test works several numbers: if at least one of the factors is divisible by a certain number, then the product is also divisible by this number. Work 24 15 77 divided by 12 , since the multiplier of this number 24 divided by 12 .

Divisibility test for a sum (difference) numbers: if each term is divisible by a certain number, then the entire sum is divided by that number. If a: b And c: b, That (a + c) : b. And if a: b, A c not divisible by b, That a+c not divisible by a number b.

If a: c And c: b, That a: b. Based on the fact that 72:24 and 24:12, we conclude that 72:12.

Representation of a number as a product of powers prime numbers called factoring a number into prime factors.

Fundamental Theorem of Arithmetic: any natural number (except 1 ) or is simple, or it can be factorized in only one way.

When decomposing a number into prime factors, the signs of divisibility are used and the “column” notation is used. In this case, the divisor is located to the right of the vertical line, and the quotient is written under the dividend.

For example, task: factor a number into prime factors 330 . Solution:

Signs of divisibility into 2, 5, 3, 9, 10, 4, 25 and 11.

There are signs of divisibility into 6, 15, 45 etc., that is, into numbers whose product can be factorized 2, 3, 5, 9 And 10 .

Greatest common divisor

The largest natural number by which each of two given natural numbers is divisible is called greatest common divisor these numbers ( GCD). For example, GCD (10; 25) = 5; and GCD (18; 24) = 6; GCD (7; 21) = 1.

If the greatest common divisor of two natural numbers is equal to 1 , then these numbers are called mutually prime.

Algorithm for finding the greatest common divisor(NOD)

GCD is often used in problems. For example, 155 notebooks and 62 pens were divided equally between students in one class. How many students are there in this class?

Solution: Finding the number of students in this class comes down to finding the greatest common divisor of the numbers 155 and 62, since the notebooks and pens were divided equally. 155 = 5 31; 62 = 2 31. GCD (155; 62) = 31.

Answer: 31 students in the class.

Least common multiple

Multiples of a natural number A is a natural number that is divisible by A without a trace. For example, number 8 has multiples: 8, 16, 24, 32 , ... Any natural number has infinitely many multiples.

Least common multiple(LCM) is the smallest natural number that is a multiple of these numbers.

Algorithm for finding the least common multiple ( NOC):

LCM is also often used in problems. For example, two cyclists simultaneously started along a cycle track in the same direction. One makes a circle in 1 minute, and the other in 45 seconds. In what minimum number of minutes after the start of the movement will they meet at the start?

Solution: The number of minutes after which they will meet again at the start must be divided by 1 min, as well as on 45 s. In 1 min = 60 s. That is, it is necessary to find the LCM (45; 60). 45 = 32 5; 60 = 22 3 5. LCM (45; 60) = 22 32 5 = 4 9 5 = 180. The result is that the cyclists will meet at the start in 180 s = 3 min.

Answer: 3 min.

Division with remainder

If a natural number A is not divisible by a natural number b, then you can do division with remainder. In this case, the resulting quotient is called incomplete. The equality is fair:

a = b n + r,

Where A- divisible, b- divider, n- incomplete quotient, r- remainder. For example, let the dividend be equal 243 , divider - 4 , Then 243: 4 = 60 (remainder 3). That is, a = 243, b = 4, n = 60, r = 3, then 243 = 60 4 + 3 .

Numbers that are divisible by 2 without remainder, are called even: a = 2n, n ∈ N.

The remaining numbers are called odd: b = 2n + 1, n ∈ N.

This is a summary of the topic "Integers. Signs of divisibility". To continue, select next steps:

• Go to next summary: