Before proceeding to the definition of the concept of the greatest common divisor (GCD), it is necessary to understand what a common divisor is in general.
It is known that an integer can have multiple divisors. We are interested in the simultaneous access to them by several integers. We consider the common divisor of several integers to be the number that can act as a divisor for each number from the specified series.
For example, the numbers 8 and 12 have the following common divisors: 1 and 4. This can be easily verified by writing mathematical expressions: 8 = 4 ⋅ 2; 12 = 3 ⋅ 4.
It should be noted that each number initially has at least two common divisors: any number is divisible by itself without a remainder, and is also divisible by 1.
Determining the Greatest Common Divisor
The Greatest Common Divisor (GCD) of two natural numbers is the largest of the natural numbers by which we can divide two of our numbers. If the value of the greatest common divisor of two natural numbers is 1, then we call these numbers coprime.
For two numbers a and b, the greatest common divisor is the number by which a and b can be divided without a remainder. This expression is written as follows: gcd (a, b) = c.
Another way to write GCD: (a, b) = c. However, in most cases, the first option is used.
So, for example, the numbers 4 and 16 have the greatest common divisor equal to 4. Let's write: gcd (4, 16) = 4.
Let's describe how we came to this result:
- We wrote out all the divisors of the number 4. We got: 4, 2, 1.
- Next, we painted all the divisors of 16. We got: 16, 8, 4, 2, 1.
- We chose divisors that are common for both 4 and 16. We got: 4, 2, 1.
- From the resulting common divisors, the largest was chosen. This is 4.
- We get the answer: for numbers 4 and 16 GCD is 4.
Similarly, you can find the GCD for three or more integers. In this case, it will be the largest integer by which you can divide all the numbers from the proposed series.
So, for example, the largest divisor for the integers 6, 12, 18, 42 will be the number 6, that is, gcd (6, 12, 18, 42) = 6. The answer was obtained using an algorithm similar to what was described above - for numbers from a series, all divisors were sequentially written out, after which the largest of them were selected.
GCD properties
The greatest common divisor has a number of properties that will be relevant for GCD of positive integers with divisors greater than zero.
Property 1
From changing places of numbers, the final value of GCD will not change. You can write this statement like this:
- gcd(a, b) = gcd(b, a).
Property 2
If a is divisible by b, then the set of common divisors of a and b is the same as the set of divisors of b. Written like this:
- gcd(a, b) = b.
The proven greatest divisor property can be used to find the gcd of two numbers when one of them is divisible by the other. In this case, the GCD is equal to one of these numbers, by which another number is divisible.
For example:
- gcd(12, 4) = 4.
Similar:
- gcd(10, 1) = 1.
Property 3
If a = bq + c, where a, b, c and q are integers, then the set of common divisors of a and b is the same as the set of common divisors of b and c.
The equality gcd (a, b) = gcd (b, c) becomes valid.
Property 4
The expression gcd(ma, mb) = m ⋅ gcd(a, b) is true provided that m is any natural number.
Property 5
Let's say p is any common divisor of a and b.
Then:
- gcd(a / p, b / p) = gcd(a, b) / p.
If p = gcd(a, b), we get:
- gcd (a / gcd (a, b), b / gcd (a, b)) = 1,
Thus, numbers a / gcd (a, b) and b / gcd (a, b) are coprime.
Property 6
Any two numbers have at least one common divisor - this is the number 1.
Knowledge of the theoretical foundations of the GCD concept, as well as practical skills in its definition, are necessary in order to work with ordinary fractions. In addition, GCD is closely related to another mathematical unit - the least common divisor. Both definitions are usually studied as part of a standard school curriculum.
