How to find gcd (greatest common divisor)

The divisor of a number is a natural number that divides another, and which results in an integer. For example, the dividers of 12 are 1, 2 , 3, 4, 6 and 12. Set of divisors of a number is always a finite set of numbers.

12: 1 = 12

12: 2 = 6

12: 4 = 3

12: 4 = 3

12 6 = 2

12: 12 = 1

D12 = { 1,2,3,4,6,12 }

The gcd (greatest common divisor), as the name implies, is the greatest common divisor of two or more numbers integers. For example, if D12 = { 1,2,3,4,6,12 } and D18 = { 1,2,3,6,9,18 }, the greatest common divisor between 12 and 18 is 6. Yet, if instead of making the gcd of 12 and 18, we do the gcd of two much larger numbers, it will take too long. Thus, instead of making the dividers of each number, there is a faster method.

Now we'll explain how to do the gcd of two or more numbers integers.

Step 1

By making the decomposition in prime factors of each number. If you don't know how to decompose a number into prime factors, click here.

Step 2

After you've decompose down each number into its prime factors, you will choose the smallest common factors. The non common factores doesnt interest.

Step 3

Calculates the product of the selected factors . The result is the greatest common divisor of the two given numbers integers.