Contents
In this article, we will consider the definition of the greatest common divisor, learn how to find it for two or more numbers, and also analyze practical examples to consolidate the material presented.
Finding the Greatest Common Divisor
Divisor of a natural number a is such a natural number bthat divides a whole (no residue). Denoted by letter Д. for example D(6) means “divisor of 6”.
If a number has more than two factors, it is called composite.
Divisor examples:
- The number 12 has the following divisors: 1, 2, 3, 4, 6.
- The number 15 has the following divisors: 1, 3, 5.
Unlike multiples, the number of divisors of a number is limited.
Common divisor of two natural numbers is the number by which both of these numbers are divisible without a remainder.
Greatest common divisor of two natural numbers – the largest number of common divisors of these numbers. Designated as NOD.
For example, the NOD (12, 24) is the greatest common divisor of 12 and 24.
Finding GCD
To find the greatest common divisor, you can use one of the methods below.
For two (or small) numbers
- We write in a row all the divisors for each number (in ascending order).
- Find the largest value that occurs in both rows. This is NOD.
Example
Let’s find the greatest divisor of the numbers 18 and 30.
Solution
D(18): 1, 2, 3, 6, 9.
D(30): 1, 2, 3, 5, 6, 10, 15.
So gcd(18, 30) = 6.
For multiple (or large) numbers
This method is usually used if you have to deal with large numbers, or if you need to find the GCD for several numbers.
- First, we decompose the numbers into prime factors – prime numbers that divide a number without a remainder.
- We note the same prime factors that occur in both layouts.
- The product of the found prime factors is the GCD.
Example
Find GCD (16, 24, 40).
Solution
Let’s decompose these numbers into prime factors.
For all three numbers, three factors are the same – these are three deuces.
Therefore gcd (16, 24, 40) = 2 ⋅ 2 ⋅ 2 = 8.