How to find the greatest common divisor of numbers

Finding the greatest common divisor: basic terms

To learn to find the greatest common divisor of two or more numbers, you need to understand that are natural, simple and complex numbers.

Natural is any number that is used when counting whole objects.

If a natural number can be divided only by itself and one, it is called simple.

All natural numbers can be divided by itself and one, but the only even Prime number is 2, all the rest can be divided into two. Therefore, a simple can only be odd numbers.

Primes quite a lot, a complete list of them does not exist. For finding GCD you can use special table with such numbers.

Most positive integers can share not only in the unit themselves, but also on other numbers. For example, the number 15 can be divided by 3 and 5. All are called divisors of the number 15.

Thus, the divisor of any natural number a is a number by which it can be divided without a remainder. If the number has more than two positive divisors, it is called composite.

The number 30 can be identified such factors as 1, 3, 5, 6, 15, 30.

You can see that 15 and 30 have the same divisors 1, 3, 5, 15. The greatest common divisor of those two numbers is 15.

Thus, a common divisor of A and B is a number that you can divide them evenly. Most can be considered the maximum number that can be divided.

To solve problems we use such abbreviated inscription:

GCD (A; B).

For example, GCD (15; 30) = 30.

To write down all the divisors of a natural number, applies to the record:

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

D (9) = {1, 9}

GCD (9; 15) = 1

In this example, the natural numbers have only one common divisor. They are called coprime, respectively, the unit is their greatest common divisor.

How to find the greatest common divisor of numbers

To find the GCD of multiple numbers, you need to:

find all divisors of each natural number individually, that is to decompose them into factors (primes);

- select all the same factors in these numbers.

- multiply them together.

For example, to calculate the greatest common divisor of 30 and 56, it is necessary to record the following:

30 = 2 * 3 * 5

70 = 2 * 5 * 7

Not to be confused with the decomposition, it is convenient to write the multiplier with the help of vertical bars. In the left part from the line you need to place the dividend and the right divider. Under severable, specify the resulting quotient.

So, in the right column will be all you need to solve the factors.

The same dividers (multipliers) for convenience to emphasize. They should rewrite and multiply and write the greatest common divisor.

30/2 70/2

15/5 35/5

7 3

NOD (30; 56) = 2 * 5 = 10

So easy actually to find the greatest common divisor of numbers. With a little practice you can do it virtually automatic.