Greatest Common Divisor (GCD): Definition, Examples, and Properties. Finding the GCD using the Euclid algorithm and using prime factorization

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$.

Decision:

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)$

But many natural numbers are evenly divisible by other natural numbers.

for example:

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.

The numbers by which the number is divisible (for 12 it is 1, 2, 3, 4, 6 and 12) are called number divisors. Divisor of a natural number a is the natural number that divides the given number a without a trace. A natural number that has more than two factors is called composite. Note that the numbers 12 and 36 have common divisors. These are the numbers: 1, 2, 3, 4, 6, 12. The largest divisor of these numbers is 12.

Common divisor of two given numbers a and b is the number by which both given numbers are divisible without a remainder a and b. Common Divisor of Multiple Numbers (GCD) is the number that serves as a divisor for each of them.

Briefly the greatest common divisor of numbers a and b are written like this:

Example: gcd (12; 36) = 12.

The divisors of numbers in the notation of the solution denote capital letter"D".

Example:

gcd (7; 9) = 1

The numbers 7 and 9 have only one common divisor - the number 1. Such numbers are called coprimechi slam.

Coprime numbers are natural numbers that have only one common divisor - the number 1. Their gcd is 1.

Greatest Common Divisor (GCD), properties.

• Main property: greatest common divisor m and n is divisible by any common divisor of these numbers. Example: for numbers 12 and 18 the greatest common divisor is 6; it is divisible by all common divisors of these numbers: 1, 2, 3, 6.
• Corollary 1: set of common divisors m and n coincides with the set of divisors gcd( m, n).
• Corollary 2: set of common multiples m and n coincides with the set of multiple LCMs ( m, n).

This means, in particular, that in order to reduce a fraction to an irreducible form, it is necessary to divide its numerator and denominator by their gcd.

• Greatest Common Divisor of Numbers m and n can be defined as the smallest positive element of the set of all their linear combinations:

and therefore represent as a linear combination of numbers m and n:

This ratio is called Bezout's ratio, and the coefficients u and v — bezout coefficients. Bézout coefficients are efficiently computed by the extended Euclid algorithm. This statement is generalized to sets of natural numbers - its meaning is that the subgroup of the group generated by the set is cyclic and is generated by one element: gcd ( a 1 , a 2 , … , a n).

Calculation of the greatest common divisor (gcd).

Efficient ways to calculate the gcd of two numbers are Euclid's algorithm and binaryalgorithm. In addition, the GCD value ( m,n) can be easily calculated if the canonical expansion of numbers is known m and n for prime factors:

where are distinct primes and and are non-negative integers (they may be zero if the corresponding prime is not in the decomposition). Then gcd ( m,n) and LCM ( m,n) are expressed by the formulas:

If there are more than two numbers: , their GCD is found according to the following algorithm:

- this is the desired GCD.

Also, in order to find greatest common divisor, you can decompose each of the given numbers into prime factors. Then write out separately only those factors that are included in all given numbers. Then we multiply the numbers written out among themselves - the result of multiplication is the greatest common divisor .

Let's analyze the calculation of the greatest common divisor step by step:

1. Decompose the divisors of numbers into prime factors:

Calculations are conveniently written using a vertical bar. To the left of the line, first write down the dividend, to the right - the divisor. Further in the left column we write down the values ​​of private. Let's explain right away with an example. Let us factorize the numbers 28 and 64 into prime factors.

2. We underline the same prime factors in both numbers:

28 = 2 . 2 . 7

64 = 2 . 2 . 2 . 2 . 2 . 2

3. We 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 arrange the location of the GCD in two ways: in a column (as was done above) or “in a line”.

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 the GCD search solution in a line. Find GCD 10 and 15.

D(10) = (1, 2, 5, 10)

D(15) = (1, 3, 5, 15)

D(10, 15) = (1, 5)

This article is about finding the greatest common divisor (gcd) two and more numbers. First, consider the Euclid algorithm, it allows you to find the GCD of two numbers. After that, we will dwell on a method that allows us to calculate the GCD of numbers as a product of their common prime factors. Next, we will deal with finding the greatest common divisor of three or more numbers, and also give examples of calculating the GCD of negative numbers.

Page navigation.

Euclid's algorithm for finding GCD

Note that if we had turned to the table of primes from the very beginning, we would have found out that the numbers 661 and 113 are prime, from which we could immediately say that their greatest common divisor is 1.

Answer:

gcd(661, 113)=1 .

Finding GCD by Factoring Numbers into Prime Factors

Consider another way to find the GCD. The greatest common divisor can be found by factoring numbers into prime factors. Let's formulate the rule: The gcd of two positive integers a and b is equal to the product of all common prime factors in the factorizations of a and b into prime factors.

Let us give an example to explain the rule for finding the GCD. Let us know the expansions of the numbers 220 and 600 into prime factors, they have the form 220=2 2 5 11 and 600=2 2 2 3 5 5 . Common prime factors involved in the expansion of the numbers 220 and 600 are 2 , 2 and 5 . Therefore gcd(220, 600)=2 2 5=20 .

Thus, if we decompose the numbers a and b into prime factors and find the product of all their common factors, then this will find the greatest common divisor of the numbers a and b.

Consider an example of finding the GCD according to the announced rule.

Example.

Find the greatest common divisor of 72 and 96.

Decision.

Let's factorize the numbers 72 and 96:

That is, 72=2 2 2 3 3 and 96=2 2 2 2 2 3 . Common prime factors are 2 , 2 , 2 and 3 . So gcd(72, 96)=2 2 2 3=24 .

Answer:

gcd(72, 96)=24 .

In conclusion of this section, we note that the validity of the above rule for finding the gcd follows from the property of the greatest common divisor, which states that GCD(m a 1 , m b 1)=m GCD(a 1 , b 1), where m is any positive integer.

Finding GCD of three or more numbers

Finding the greatest common divisor of three or more numbers can be reduced to successively 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 is equal to the number d k , which is found in sequential calculation 1 , a k)=d k .

Let's see how the process of finding the GCD of several numbers looks like by considering the solution of the example.

Example.

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

Decision.

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

First, using the Euclid algorithm, we determine the greatest common divisor d 2 of the 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 \u003d GCD (d 2, a 3) \u003d GCD (6, 570). Again we apply the Euclid algorithm: 570=6·95 , therefore, d 3 =GCD(6, 570)=6 .

It remains to calculate d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36). Since 36 is divisible by 6, then d 4 \u003d GCD (6, 36) \u003d 6.

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

Answer:

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

Decomposing 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.

Decision.

We decompose the numbers 78 , 294 , 570 and 36 into 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.

Let's solve the problem. We have two types of cookies. Some are chocolate and some are plain. There are 48 chocolate pieces, and simple 36. It is necessary to make the maximum possible number of gifts from these cookies, and all of them must be used.

First, let's write down all the divisors of each of these two numbers, since both of these numbers must be divisible by the number of gifts.

We get

• 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
• 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.

Let's find among the divisors the common ones that both the first and the second number have.

Common divisors will be: 1, 2, 3, 4, 6, 12.

The greatest common divisor of all is 12. This number is called the greatest common divisor of 36 and 48.

Based on the result, we can conclude that 12 gifts can be made from all cookies. One such gift will contain 4 chocolate cookies and 3 regular cookies.

Finding the Greatest Common Divisor

• The largest natural number by which two numbers a and b are divisible without a remainder is called the greatest common divisor of these numbers.

Sometimes the abbreviation GCD is used to abbreviate the entry.

Some pairs of numbers have one as their greatest common divisor. Such numbers are called coprime numbers. For example, numbers 24 and 35. Have GCD =1.

How to find the greatest common divisor

In order to find the greatest common divisor, it is not necessary to write out all the divisors of these numbers.

You can do otherwise. First, factor both numbers into prime factors.

• 48 = 2*2*2*2*3,
• 36 = 2*2*3*3.

Now, from the factors that are included in the expansion of the first number, we delete all those that are not included in the expansion of the second number. In our case, these are two deuces.

• 48 = 2*2*2*2*3 ,
• 36 = 2*2*3 *3.

The factors 2, 2 and 3 remain. Their product is 12. This number will be the greatest common divisor of the numbers 48 and 36.

This rule can be extended to the case of three, four, and so on. numbers.

General scheme for finding the greatest common divisor

• 1. Decompose numbers into prime factors.
• 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. Calculate the product of the remaining factors.