To learn how to find the greatest common divisor of two or more numbers, you need to understand what natural, prime and complex numbers are.
A natural number is any number that is used to count whole objects.
If a natural number can only be divided into itself and one, then it is called prime.
All natural numbers can be divided by themselves and one, but the only even prime number is 2, all others can be divided by two. Therefore, only odd numbers can be prime.
There are a lot of prime numbers full list they don't exist. To find GCD it is convenient to use special tables with such numbers.
Majority natural numbers can be divided not only by one, themselves, but also by other numbers. So, for example, the number 15 can be divided by 3 and 5. All of them are called divisors of the number 15.
Thus, the divisor of any A is the number by which it can be divided without a remainder. If a number has more than two natural factors, it is called composite.
The number 30 can have divisors such as 1, 3, 5, 6, 15, 30.
You will notice that 15 and 30 have the same divisors 1, 3, 5, 15. The greatest common divisor of these two numbers is 15.
Thus, the common divisor of the numbers A and B is the number by which they can be divided entirely. The largest can be considered the maximum total number, into which they can be divided.
To solve problems, the following abbreviated inscription is used:
GCD (A; B).
For example, gcd (15; 30) = 30.
To write down all the divisors of a natural number, use the notation:
D (15) = (1, 3, 5, 15)
GCD (9; 15) = 1
In this example, the natural numbers have only one common divisor. They are called relatively prime, so unity is their greatest common divisor.
How to find the greatest common divisor of numbers
To find the gcd of several numbers, you need:
Find all divisors of each natural number separately, that is, factor them into factors (prime numbers);
Select all identical factors of given numbers;
Multiply them together.
For example, to calculate the greatest common divisor of the numbers 30 and 56, you would write the following:
To avoid confusion, it is convenient to write factors using vertical columns. On the left side of the line you need to place the dividend, and on the right side - the divisor. Under the dividend, you should indicate the resulting quotient.
So, in the right column there will be all the factors needed for the solution.
Identical divisors (found factors) can be underlined for convenience. They should be rewritten and multiplied and the greatest common divisor written down.
GCD (30; 56) = 2 * 5 = 10
This is how easy it really is to find the greatest common divisor of numbers. If you practice a little, you can do this almost automatically.
From now on we will assume that at least one of these numbers is non-zero. If all given numbers are equal to zero, then their common divisor is any integer, and since there are infinitely many integers, we cannot talk about the greatest of them. Therefore, we cannot talk about the greatest common divisor of numbers, each of which is equal to zero.
Now we can give determining the greatest common divisor two numbers.
Definition.
Greatest common divisor two integers is the largest integer dividing two given integers.
To briefly write the greatest common divisor, the abbreviation GCD is often used - Greatest Common Divisor. Also, the greatest common divisor of two numbers a and b is often denoted as GCD(a, b) .
Let's give example of greatest common divisor (GCD) two integers. The greatest common divisor of the numbers 6 and −15 is 3. Let's justify this. Let's write down all the divisors of the number six: ±6, ±3, ±1, and the divisors of the number −15 are the numbers ±15, ±5, ±3 and ±1. Now you can find all the common divisors of the numbers 6 and −15, these are the numbers −3, −1, 1 and 3. Since −3<−1<1<3 , то 3 – это наибольший общий делитель чисел 6 и −15 . То есть, НОД(6, −15)=3 .
Determining the greatest common divisor of three and more integers is similar to determining the gcd of two numbers.
Definition.
Greatest common divisor three or more integers is the largest integer dividing all given numbers at the same time.
We will denote the greatest common divisor of n integers a 1 , a 2 , …, a n as GCD(a 1 , a 2 , …, a n) . If the value b of the greatest common divisor of these numbers is found, then we can write GCD(a 1 , a 2 , …, a n)=b.
As an example, let's give the gcd of four integers −8, 52, 16 and −12, it is equal to 4, that is, gcd(−8, 52, 16, −12)=4. This can be checked by writing down all the divisors of the given numbers, choosing common ones from them and determining the greatest common divisor.
Note that the greatest common divisor of integers can be equal to one of these numbers. This statement is true if all given numbers are divisible by one of them (the proof is given in the next paragraph of this article). For example, GCD(15, 60, −45)=15. This is true, since 15 divides both the number 15, and the number 60, and the number −45, and there is no common divisor of the numbers 15, 60 and −45 that exceeds 15.
Of particular interest are the so-called relatively prime numbers - those integers whose greatest common divisor is equal to one.
Properties of the greatest common divisor, Euclidean algorithm
The greatest common divisor has a number of characteristic results, in other words, a number of properties. Now we will list the main properties of the greatest common divisor (GCD), we will formulate them in the form of theorems and immediately provide proofs.
We will formulate all the properties of the greatest common divisor for positive integers, and we will consider only the positive divisors of these numbers.
The greatest common divisor of the numbers a and b is equal to the greatest common divisor of the numbers b and a , that is, gcd(a, b) = gcd(a, b) .
This property of GCD follows directly from the definition of the greatest common divisor.
If a is divisible by b, then the set of common divisors of the numbers a and b coincides with the set of divisors of the number b, in particular, gcd(a, b)=b.
Proof.
Any common divisor of the numbers a and b is a divisor of each of these numbers, including the number b. On the other hand, since a is a multiple of b, then any divisor of the number b is a divisor of the number a due to the fact that divisibility has the property of transitivity, therefore, any divisor of the number b is a common divisor of the numbers a and b. This proves that if a is divisible by b, then the set of divisors of the numbers a and b coincides with the set of divisors of one number b. And since greatest divisor number b is the number b itself, then the greatest common divisor of the numbers a and b is also equal to b, that is, gcd(a, b)=b.
In particular, if the numbers a and b are equal, then gcd(a, b)=gcd(a, a)=gcd(b, b)=a=b. For example, GCD(132, 132)=132.
The proven property of the greatest divisor allows us to find the gcd of two numbers when one of them is divided by the other. In this case, GCD is equal to one of these numbers, which is divided by another number. For example, GCD(8, 24)=8, since 24 is a multiple of eight.
If a=b·q+c, where a, b, c and q are integers, then the set of common divisors of the numbers a and b coincides with the set of common divisors of the numbers b and c, in particular, gcd(a, b)=gcd (b, c) .
Let us justify this property of GCD.
Since the equality a=b·q+c holds, then every common divisor of the numbers a and b also divides c (this follows from the properties of divisibility). For the same reason, every common divisor of b and c divides a. Therefore, the set of common divisors of the numbers a and b coincides with the set of common divisors of the numbers b and c. In particular, the greatest of these common divisors must also coincide, that is, the following equality GCD(a, b) = GCD(b, c) must be true.
Now we will formulate and prove the theorem, which is Euclidean algorithm. The Euclid algorithm allows you to find the GCD of two numbers (see finding the GCD using the Euclid algorithm). Moreover, the Euclid algorithm will allow us to prove the following properties of the greatest common divisor.
Before giving the formulation of the theorem, we recommend refreshing your memory of the theorem from the theory section, which states that the dividend a can be represented as b q + r, where b is a divisor, q is some integer called an incomplete quotient, and r is an integer that satisfies the condition, called the remainder.
So, let a series of equalities be true for two non-zero positive integers a and b 
ending when r k+1 =0 (which is inevitable, since b>r 1 >r 2 >r 3 , ... is a series of decreasing integers, and this series cannot contain more than final number positive numbers), then r k is the greatest common divisor of the numbers a and b, that is, r k = GCD(a, b) .
Proof.
Let us first prove that r k is a common divisor of the numbers a and b, after which we will show that r k is not just a divisor, but the greatest common divisor of the numbers a and b.
We will move along the written equalities from bottom to top. From the last equality we can say that r k−1 is divisible by r k . Taking into account this fact, as well as the previous property of GCD, the penultimate equality r k−2 =r k−1 ·q k +r k allows us to state that r k−2 is divisible by r k, since r k−1 is divisible by r k and r k is divisible by r k. By analogy, from the third equality from below we conclude that r k−3 is divisible by r k . And so on. From the second equality we obtain that b is divisible by r k , and from the first equality we obtain that a is divisible by r k . Therefore, r k is a common divisor of the numbers a and b.
It remains to prove that r k = GCD(a, b) . For it is enough to show that any common divisor of the numbers a and b (let’s denote it r 0 ) divides r k .
We will move along the original equalities from top to bottom. Due to the previous property, it follows from the first equality that r 1 is divisible by r 0. Then from the second equality we obtain that r 2 is divisible by r 0 . And so on. From the last equality we obtain that r k is divisible by r 0 . Thus, r k = GCD(a, b) .
From the considered property of the greatest common divisor it follows that the set of common divisors of the numbers a and b coincides with the set of divisors of the greatest common divisor of these numbers. This corollary from Euclid's algorithm allows us to find all common divisors of two numbers as divisors of the gcd of these numbers.
Let a and b be integers, not simultaneously equal to zero, then there are such integers u 0 and v 0 , then the equality GCD(a, b)=a·u 0 +b·v 0 is true. The last equality is a linear representation of the greatest common divisor of the numbers a and b, this equality is called the Bezout relation, and the numbers u 0 and v 0 are called the Bezout coefficients.
Proof.
Using the Euclidean algorithm we can write the following equalities
From the first equality we have r 1 =a−b·q 1, and, denoting 1=s 1 and −q 1 =t 1, this equality takes the form r 1 =s 1 ·a+t 1 ·b, and the numbers s 1 and t 1 are integers. Then from the second equality we obtain r 2 =b−r 1 ·q 2 = b−(s 1 ·a+t 1 ·b)·q 2 =−s 1 ·q 2 ·a+(1−t 1 ·q 2)·b. Denoting −s 1 ·q 2 =s 2 and 1−t 1 ·q 2 =t 2, the last equality can be written as r 2 =s 2 ·a+t 2 ·b, and s 2 and t 2 are integers (since the sum, difference and product of integers is an integer). Similarly, from the third equality we obtain r 3 =s 3 ·a+t 3 ·b, from the fourth equality r 4 =s 4 ·a+t 4 ·b, and so on. Finally, r k =s k ·a+t k ·b, where s k and t k are integers. Since r k =GCD(a, b) , and denoting s k =u 0 and t k =v 0 , we obtain a linear representation of GCD of the required form: GCD(a, b)=a·u 0 +b·v 0 .
If m is any natural number, then GCD(m a, m b)=m GCD(a, b).
The rationale for this property of the greatest common divisor is as follows. If we multiply by m both sides of each of the equalities of the Euclidean algorithm, we obtain that GCD(m·a, m·b)=m·r k , and r k is GCD(a, b) . Hence, GCD(m a, m b)=m GCD(a, b).
The method of finding GCD using prime factorization is based on this property of the greatest common divisor.
Let p be any common divisor of numbers a and b, then gcd(a:p, b:p)=gcd(a, b):p, in particular, if p=GCD(a, b) we have gcd(a:gcd(a, b), b:gcd(a, b))=1, that is, the numbers a:GCD(a, b) and b:GCD(a, b) are relatively prime.
Since a=p·(a:p) and b=p·(b:p) , and due to the previous property, we can write a chain of equalities of the form GCD(a, b)=GCD(p (a:p), p (b:p))= p·GCD(a:p, b:p) , from which the equality being proved follows.
The property of the greatest common divisor that we just proved is the basis of .
Now let’s talk about the GCD property, which reduces the problem of finding the greatest common divisor of three or more numbers to sequentially finding the GCD of two numbers.
The greatest common divisor of the numbers a 1 , a 2 , …, a k is equal to the number d k , which is found by sequentially calculating 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 .
The proof is based on a corollary of the Euclidean algorithm. The common divisors of the numbers a 1 and a 2 coincide with the divisors of d 2. Then the common divisors of the numbers a 1, a 2 and a 3 coincide with the common divisors of the numbers d 2 and a 3, therefore, they coincide with the divisors of d 3. The common divisors of the numbers a 1, a 2, a 3 and a 4 coincide with the common divisors of d 3 and a 4, therefore, they coincide with the divisors of d 4. And so on. Finally, the common divisors of the numbers a 1, a 2, ..., a k coincide with the divisors d k. And since the greatest divisor of the number d k is the number d k itself, then GCD(a 1 , a 2 , …, a k)=d k.
This concludes our review of the basic properties of the greatest common divisor.
References.
- 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.
The online calculator allows you to quickly find the greatest common divisor and least common multiple for two or any other number of numbers.
Calculator for finding GCD and LCM
Find GCD and LOC
Found GCD and LOC: 5806
How to use the calculator
- Enter numbers in the input field
- If you enter incorrect characters, the input field will be highlighted in red
- click the "Find GCD and LOC" button
How to enter numbers
- Numbers are entered separated by a space, period or comma
- The length of entered numbers is not limited, so finding GCD and LCM of long numbers is not difficult
What are GCD and NOC?
Greatest common divisor several numbers is the largest natural integer by which all original numbers are divisible without a remainder. The greatest common divisor is abbreviated as GCD.
Least common multiple several numbers is smallest number, which is divisible by each of the original numbers without a remainder. The least common multiple is abbreviated as NOC.
How to check that a number is divisible by another number without a remainder?
To find out whether one number is divisible by another without a remainder, you can use some properties of divisibility of numbers. Then, by combining them, you can check the divisibility of some of them and their combinations.
Some signs of divisibility of numbers
1. Divisibility test for a number by 2
To determine whether a number is divisible by two (whether it is even), it is enough to look at the last digit of this number: if it is equal to 0, 2, 4, 6 or 8, then the number is even, which means it is divisible by 2.
Example: determine whether the number 34938 is divisible by 2.
Solution: look at the last digit: 8 means the number is divisible by two.
2. Divisibility test for a number by 3
A number is divisible by 3 when the sum of its digits is divisible by three. Thus, to determine whether a number is divisible by 3, you need to calculate the sum of the digits and check whether it is divisible by 3. Even if the sum of the digits is very large, you can repeat the same process again.
Example: determine whether the number 34938 is divisible by 3.
Solution: We count the sum of the numbers: 3+4+9+3+8 = 27. 27 is divisible by 3, which means the number is divisible by three.
3. Divisibility test for a number by 5
A number is divisible by 5 when its last digit is zero or five.
Example: determine whether the number 34938 is divisible by 5.
Solution: look at the last digit: 8 means the number is NOT divisible by five.
4. Divisibility test for a number by 9
This sign is very similar to the sign of divisibility by three: a number is divisible by 9 when the sum of its digits is divisible by 9.
Example: determine whether the number 34938 is divisible by 9.
Solution: We count the sum of the numbers: 3+4+9+3+8 = 27. 27 is divisible by 9, which means the number is divisible by nine.
How to find GCD and LCM of two numbers
How to find the gcd of two numbers
Most in a simple way Calculating the greatest common divisor of two numbers is to find all possible divisors of these numbers and select the largest of them.
Let's consider this method using the example of finding GCD(28, 36):
- We factor both numbers: 28 = 1·2·2·7, 36 = 1·2·2·3·3
- We find common factors, that is, those that both numbers have: 1, 2 and 2.
- We calculate the product of these factors: 1 2 2 = 4 - this is the greatest common divisor of the numbers 28 and 36.
How to find the LCM of two numbers
There are two most common ways to find the least multiple of two numbers. The first method is that you can write down the first multiples of two numbers, and then choose among them a number that will be common to both numbers and at the same time the smallest. And the second is to find the gcd of these numbers. Let's consider only it.
To calculate the LCM, you need to calculate the product of the original numbers and then divide it by the previously found GCD. Let's find the LCM for the same numbers 28 and 36:
- Find the product of numbers 28 and 36: 28·36 = 1008
- GCD(28, 36), as already known, is equal to 4
- LCM(28, 36) = 1008 / 4 = 252 .
Finding GCD and LCM for several numbers
The greatest common divisor can be found for several numbers, not just two. For this purpose, the numbers to be found for the greatest common divisor are decomposed into prime factors, then find the product of the common prime factors of these numbers. You can also use the following relation to find the gcd of several numbers: GCD(a, b, c) = GCD(GCD(a, b), c).
A similar relationship applies to the least common multiple: LCM(a, b, c) = LCM(LCM(a, b), c)
Example: find GCD and LCM for numbers 12, 32 and 36.
- First, let's factor the numbers: 12 = 1·2·2·3, 32 = 1·2·2·2·2·2, 36 = 1·2·2·3·3.
- Let's find the common factors: 1, 2 and 2.
- Their product will give GCD: 1·2·2 = 4
- Now let’s find the LCM: to do this, let’s first find the LCM(12, 32): 12·32 / 4 = 96 .
- To find the NOC of everyone three numbers, you need to find GCD(96, 36): 96 = 1·2·2·2·2·2·3 , 36 = 1·2·2·3·3 , GCD = 1·2·2·3 = 12 .
- LCM(12, 32, 36) = 96·36 / 12 = 288.
Divisibility criteria for natural numbers.
Numbers divisible by 2 without a remainder are calledeven .
Numbers that are not evenly divisible by 2 are calledodd .
Test for divisibility by 2
If a natural number ends with an even digit, then this number is divisible by 2 without a remainder, and if a number ends with an odd digit, then this number is not evenly divisible by 2.
For example, the numbers 60 , 30 8 , 8 4 are divisible by 2 without remainder, and the numbers are 51 , 8 5 , 16 7 are not divisible by 2 without a remainder.
Test for divisibility by 3
If the sum of the digits of a number is divisible by 3, then the number is divisible by 3; If the sum of the digits of a number is not divisible by 3, then the number is not divisible by 3.
For example, let’s find out whether the number 2772825 is divisible by 3. To do this, let’s calculate the sum of the digits of this number: 2+7+7+2+8+2+5 = 33 - divisible by 3. This means the number 2772825 is divisible by 3.
Divisibility test by 5
If the record of a natural number ends with the digit 0 or 5, then this number is divisible by 5 without a remainder. If the record of a number ends with another digit, then the number is not divisible by 5 without a remainder.
For example, the numbers 15 , 3 0 , 176 5 , 47530 0 are divisible by 5 without remainder, and the numbers are 17 , 37 8 , 9 1 don't share.
Divisibility test by 9
If the sum of the digits of a number is divisible by 9, then the number is divisible by 9; If the sum of the digits of a number is not divisible by 9, then the number is not divisible by 9.
For example, let’s find out whether the number 5402070 is divisible by 9. To do this, let’s calculate the sum of the digits of this number: 5+4+0+2+0+7+0 = 16 - not divisible by 9. This means the number 5402070 is not divisible by 9.
Divisibility test by 10
If a natural number ends with the digit 0, then this number is divisible by 10 without a remainder. If a natural number ends with another digit, then it is not evenly divisible by 10.
For example, the numbers 40 , 17 0 , 1409 0 are divisible by 10 without remainder, and the numbers 17 , 9 3 , 1430 7 - don't share.
The rule for finding the greatest common divisor (GCD).
To find the greatest common divisor of several natural numbers, you need to:
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.
Example. Let's find GCD (48;36). Let's use the rule.
1. Let's factor the numbers 48 and 36 into prime factors.
48 = 2 · 2 · 2 · 2 · 3
36 = 2 · 2 · 3 · 3
2. From the factors included in the expansion of the number 48, we delete those that are not included in the expansion of the number 36.
48 = 2 · 2 · 2 · 2 · 3
The remaining factors are 2, 2 and 3.
3. Multiply the remaining factors and get 12. This number is the greatest common divisor of the numbers 48 and 36.
GCD (48;36) = 2· 2 · 3 = 12.
The rule for finding the least common multiple (LCM).
To find the least common multiple of several natural numbers, you need to:
1) factor them into prime factors;
2) write down 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.
Example. Let's find the LOC (75;60). Let's use the rule.
1. Let's factor the numbers 75 and 60 into prime factors.
75 = 3 · 5 · 5
60 = 2 · 2 · 3 · 3
2. Let’s write down the factors included in the expansion of the number 75: 3, 5, 5.
LCM(75;60) = 3 · 5 · 5 · …
3. Add to them the missing factors from the expansion of the number 60, i.e. 2, 2.
LCM(75;60) = 3 · 5 · 5 · 2 · 2
4. Find the product of the resulting factors
LCM(75;60) = 3 · 5 · 5 · 2 · 2 = 300.
This article is devoted to the issue of finding the greatest common divisor. First we will explain what it is and give several examples, introduce definitions of the greatest common divisor of 2, 3 or more numbers, and then dwell on the general properties this concept and we will prove them.
Yandex.RTB R-A-339285-1
What are common divisors
To understand what the greatest common divisor is, we first formulate what a common divisor for integers generally is.
In the article about multiples and divisors, we said that an integer always has several divisors. Here we are interested in the divisors of a certain number of integers at once, especially those common (identical) for all. Let's write down the basic definition.
Definition 1
The common divisor of several integers is a number that can be a divisor of each number from the specified set.
Example 1
Here are examples of such a divisor: three will be a common divisor for the numbers - 12 and 9, since the equalities 9 = 3 · 3 and − 12 = 3 · (− 4) are true. The numbers 3 and - 12 have other common factors, such as 1, − 1 and − 3. Let's take another example. The four integers 3, − 11, − 8 and 19 will have two common factors: 1 and - 1.
Knowing the properties of divisibility, we can say that any integer can be divided by one and minus one, which means that any set of integers will already have at least two common divisors.
Also note that if we have a common divisor b for several numbers, then the same numbers can be divided by the opposite number, that is, by - b. In principle, we can only take positive divisors, then all common divisors will also be greater than 0. This approach can also be used, but completely ignored negative numbers shouldn't.
What is the greatest common divisor (GCD)
According to the properties of divisibility, if b is a divisor of an integer a that is not equal to 0, then the modulus of b cannot be greater than the modulus of a, therefore, any number not equal to 0 has a finite number of divisors. This means that the number of common divisors of several integers, at least one of which is different from zero, will also be finite, and from their entire set we can always select the largest number (we have already talked about the concept of the largest and smallest integer, we advise you to repeat this material).
In further discussions we will assume that at least one of the set of numbers for which we need to find the greatest common divisor will be different from 0. If they are all equal to 0, then their divisor can be any integer, and since there are infinitely many of them, we cannot choose the largest one. In other words, it is impossible to find the greatest common divisor for a set of numbers equal to 0.
Let's move on to the formulation of the main definition.
Definition 2
The greatest common divisor of several numbers is the largest integer that divides all those numbers.
In writing, the greatest common divisor is most often denoted by the abbreviation GCD. For two numbers it can be written as gcd (a, b).
Example 2
What is an example of a gcd for two integers? For example, for 6 and - 15 it would be 3. Let's justify this. First, we write down all the divisors of six: ± 6, ± 3, ± 1, and then all the divisors of fifteen: ± 15, ± 5, ± 3 and ± 1. After that, we choose the common ones: these are − 3, − 1, 1 and 3. Of these, you need to choose the largest number. This will be 3.
For three or more numbers, determining the greatest common factor will be almost the same.
Definition 3
The greatest common divisor of three or more numbers will be the largest integer that will divide all of these numbers at the same time.
For numbers a 1, a 2, …, a n, it is convenient to denote the divisor as GCD (a 1, a 2, …, a n). The value of the divisor itself is written as GCD (a 1, a 2, ..., a n) = b.
Example 3
Here are examples of the greatest common divisor of several integers: 12, - 8, 52, 16. It will be equal to four, which means we can write that GCD (12, - 8, 52, 16) = 4.
You can check the correctness of this statement by writing down all the divisors of these numbers and then choosing the largest of them.
In practice, there are often cases when the greatest common divisor is equal to one of the numbers. This happens when all other numbers can be divided by a given number (in the first paragraph of the article we provided a proof of this statement).
Example 4
Thus, the greatest common divisor of the numbers 60, 15 and - 45 is 15, since fifteen is divisible not only by 60 and - 45, but also by itself, and there is no greater divisor for all these numbers.
A special case consists of coprime numbers. They are integers with a greatest common divisor of 1.
Basic properties of GCD and Euclidean algorithm
The greatest common divisor has some characteristic properties. Let us formulate them in the form of theorems and prove each of them.
Note that these properties are formulated for integers greater than zero, and we will consider only positive divisors.
Definition 4
The numbers a and b have a greatest common divisor equal to gcd for b and a, that is, gcd (a, b) = gcd (b, a). Reversing numbers does not affect the final result.
This property follows from the very definition of GCD and does not need proof.
Definition 5
If the number a can be divided by the number b, then the set of common divisors of these two numbers will be similar to the set of divisors of the number b, that is, gcd (a, b) = b.
Let's prove this statement.
Evidence 1
If the numbers a and b have common divisors, then either of them can be divided by them. At the same time, if a is a multiple of b, then any divisor of b will also be a divisor of a, since divisibility has such a property as transitivity. This means that any divisor b will be common to the numbers a and b. This proves that if we can divide a by b, then the set of all divisors of both numbers will coincide with the set of divisors of one number b. And since the greatest divisor of any number is this number itself, then the greatest common divisor of the numbers a and b will also be equal to b, i.e. GCD (a , b) = b . If a = b, then gcd (a, b) = gcd (a, a) = gcd (b, b) = a = b, for example, gcd (132, 132) = 132.
Using this property, we can find the greatest common divisor of two numbers if one of them can be divided by the other. This divisor is equal to one of these two numbers by which the second number can be divided. For example, gcd (8, 24) = 8, since 24 is a multiple of eight.
Definition 6 Proof 2
Let's try to prove this property. We initially have the equality a = b q + c, and any common divisor of a and b will also divide c, which is explained by the corresponding divisibility property. Therefore, any common divisor of b and c will divide a. This means that the set of common divisors a and b will coincide with the set of divisors b and c, including the largest of them, which means that the equality gcd (a, b) = gcd (b, c) is true.
Definition 7
The following property is called the Euclidean algorithm. With its help, you can calculate the greatest common divisor of two numbers, as well as prove other properties of GCD.
Before formulating the property, we advise you to repeat the theorem that we proved in the article on division with a remainder. According to it, the divisible number a can be represented as b · q + r, with b here being a divisor, q being some integer (also called an incomplete quotient), and r being a remainder that satisfies the condition 0 ≤ r ≤ b.
Let's say we have two integers greater than 0, for which the following equalities will be true:
a = b q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1
These equalities end when r k + 1 becomes equal to 0. This will definitely happen, since the sequence b > r 1 > r 2 > r 3, ... is a series of decreasing integers, which can only include a finite number of them. This means that r k is the greatest common divisor of a and b, that is, r k = gcd (a, b).
First of all, we need to prove that r k is a common divisor of the numbers a and b, and after that, that r k is not just a divisor, but rather the greatest common divisor of two given numbers.
Let's look at the list of equalities above, from bottom to top. According to the last equality,
r k − 1 can be divided by r k . Based on this fact, as well as the previous proven property of the greatest common divisor, it can be argued that r k − 2 can be divided by r k , since
r k − 1 is divided by r k and r k is divided by r k .
The third equality from below allows us to conclude that r k − 3 can be divided by r k , etc. The second from the bottom is that b is divisible by r k , and the first is that a is divisible by r k . From all this we conclude that r k is the common divisor of a and b.
Now let's prove that r k = GCD (a , b) . What needs to be done for this? Show that any common divisor of a and b will divide r k. Let's denote it r 0 .
Let's look at the same list of equalities, but from top to bottom. Based on the previous property, we can conclude that r 1 is divisible by r 0, which means, according to the second equality, r 2 is divided by r 0. We go down all the equalities and from the last we conclude that r k is divisible by r 0 . Therefore, r k = gcd (a , b) .
Having considered this property, we conclude that the set of common divisors a and b is similar to the set of GCD divisors of these numbers. This statement, which is a consequence of Euclidean's algorithm, will allow us to calculate all common divisors of two given numbers.
Let's move on to other properties.
Definition 8
If a and b are integers not equal to 0, then there must be two other integers u 0 and v 0 for which the equality GCD (a, b) = a · u 0 + b · v 0 will be valid.
The equality given in the property statement is a linear representation of the greatest common divisor of a and b. It is called the Bezout relation, and the numbers u 0 and v 0 are called the Bezout coefficients.
Evidence 3
Let's prove this property. Let us write down the sequence of equalities using the Euclidean algorithm:
a = b q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1
The first equality tells us that r 1 = a − b · q 1 . Let us denote 1 = s 1 and − q 1 = t 1 and rewrite this equality in the form r 1 = s 1 · a + t 1 · b. Here the numbers s 1 and t 1 will be integers. The second equality allows us to conclude that r 2 = b − r 1 · q 2 = b − (s 1 · a + t 1 · b) · q 2 = − s 1 · q 2 · a + (1 − t 1 · q 2) b . Let us denote − s 1 · q 2 = s 2 and 1 − t 1 · q 2 = t 2 and rewrite the equality as r 2 = s 2 · a + t 2 · b, where s 2 and t 2 will also be integers. This is because the sum of integers, their product and difference are also integers. In exactly the same way we obtain from the third equality r 3 = s 3 · a + t 3 · b, from the next one r 4 = s 4 · a + t 4 · b, etc. In the end we conclude that r k = s k · a + t k · b for integer s k and t k . Since r k = GCD (a, b), we denote s k = u 0 and t k = v 0. As a result, we can obtain a linear representation of GCD in the required form: GCD (a, b) = a · u 0 + b · v 0.
Definition 9
GCD (m a, m b) = m GCD (a, b) for any natural value of m.
Proof 4
This property can be justified as follows. Let's multiply both sides of each equality in the Euclidean algorithm by the number m and get that GCD (m · a, m · b) = m · r k, and r k is GCD (a, b). This means gcd (m a, m b) = m gcd (a, b). It is this property of the greatest common divisor that is used when finding the GCD using the method of factorization.
Definition 10
If the numbers a and b have a common divisor p, then gcd (a: p, b: p) = gcd (a, b): p. In the case where p = GCD (a, b) we obtain GCD (a: GCD (a, b), b: GCD (a, b) = 1, therefore, the numbers a: GCD (a, b) and b: GCD (a , b) are relatively prime.
Since a = p (a: p) and b = p (b: p), then, based on the previous property, we can create equalities of the form gcd (a, b) = gcd (p (a: p), p · (b: p)) = p · GCD (a: p , b: p) , among which the proof will be of this property. We use this statement when we give common fractions to irreducible form.
Definition 11
The greatest common divisor of a 1, a 2, …, a k will be the number d k, which can be found by sequentially calculating 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 .
This property is useful when finding the greatest common divisor of three or more numbers. Using it, you can reduce this action to operations with two numbers. Its basis is a corollary from the Euclidean algorithm: if the set of common divisors a 1, a 2 and a 3 coincides with the set d 2 and a 3, then it will also coincide with the divisors d 3. The divisors of the numbers a 1, a 2, a 3 and a 4 will coincide with the divisors of d 3, which means they will also coincide with the divisors of d 4, etc. In the end, we get that the common divisors of the numbers a 1, a 2, ..., a k will coincide with the divisors d k, and since the greatest divisor of the number d k will be this number itself, then GCD (a 1, a 2, ..., a k) = d k.
That's all we would like to tell you about the properties of the greatest common divisor.
If you notice an error in the text, please highlight it and press Ctrl+Enter
