The greatest common divisor of numbers n_{1},\\; n_{2}, \\cdots,\\; n_{x} is a number, which divides all numbers given and is maximal.

Computing the greatest common divisor

Factorization

The easiest way to compute the greatest common divisor of numbers n_{1},\\; n_{2}, \\cdots,\\; n_{x} is to express them as a product of prime numbers (factorize them). If we multiply together all prime factors in their highest common power, we get a greatest common divisor of the original numbers.

Example

Find the greatest common divisor of numbers 72, 48 and 54?

72 = 2\\cdot 2\\cdot 2\\cdot 3\\cdot 3 = 2^{3} \\cdot  3^{2}
48 = 2\\cdot 2\\cdot 2\\cdot 2\\cdot 3 = 2^{4} \\cdot  3^{1}
54 = 2\\cdot 3\\cdot 3\\cdot 3 = 2^{1} \\cdot  3^{3}
gcd(72,\\; 48,\\; 54) = 2^{1}\\cdot 3^{1} = 2\\cdot 3 = 6

Example

Find the greatest common divisor of numbers 288 and 420?

288 = 2 \\cdot 2 \\cdot 2 \\cdot 2 \\cdot 2 \\cdot 3 \\cdot 3 = 2^{5} \\cdot 3^{2}
420 = 2 \\cdot 2 \\cdot 3 \\cdot 5 \\cdot 7 = 2^{2} \\cdot  3^{1} \\cdot  5^{1} \\cdot 7^{1}
gcd(288,\\; 420) = 2^{2}\\cdot 3^{1} = 2 \\cdot 2 \\cdot 3 = 12

We can visualize this approach using the Venn diagram, in which is each number represented as a set of its factors. We may find the greatest common divisor in the intersection of these sets.

The greatest common divisor using Venn diagram
The greatest common divisor using Venn diagram

Euclidean algorithm

The integer factorization is computationally a very expensive operation. Hence we use the Euclidean algorithm (Euclid's algorithm) to calculate the greatest common divisor of two natural numbers. The Euclidean algorithm does not require any factorization at all.

Description

The Euclidean algorithm takes as an input two positive integers A and B and assumes that gcd(A, B) = gcd(B,\\; A\\; \\%\\; B)) (\\% denotes a modulo operation). This theorem can be easily proven.

In each step the algorithm divides A by B. If the remainder is not equal to 0, then the procedure sets a value of B into the variable A and the remainder into the variable B and repeats the step (division).

If the remainder is equal to 0, then the algorithm returns value stored in B (it is the greatest common divisor of original numbers A and B).

Example

Find the greatest common divisor of numbers 133 and 15?

A = x \\cdot B + remainder
133 = 8 \\cdot 15 + 13
15 = 1 \\cdot 13 + 2
13 = 6 \\cdot 2 + 1
2 = 2 \\cdot 1 + 0
gcd(133, \\; 15) = 1

Příklad

Find the greatest common divisor of numbers 140 and 15?

A = x \\cdot B + remainder
140 = 9 \\cdot 15 + 5
15 = 3 \\cdot 5 + 0
gcd(140, \\; 15) = 5

The least common multiple

The greatest common divisor of two numbers might be used to compute the least common multiple of the same numbers using the following formula:


lcm(n_{1},\\; n_{2}) = {{n_{1} \\cdot n_{2}} \\over {gcd(n_{1},\\; n_{2})} }

Example

Find the least common multiple of numbers 140 a 15?

gcd(140,\\; 15) = 5
lcm(140,\\; 15) = {{140 \\cdot 15} \\over {gcd(140,\\; 15)}} = {{2100} \\over {5}} = 420

Code

/**
 * Input: Numbers a > 0, b > 0
 * Output: gcd(a, b)
 */
function gcd(a, b)
    if a >= b then
        m = a
        n = b
    else
        m = b
        n = a

    while n != 0 do 
        m = p*n + z
        m = n
        n = z

    return m
    /**
     * Returns the greatest common divisor of the given numbers
     * @param a number 1
     * @param b number 2
     * @return gcd(a, b)
     */
    public static int gcd(int a, int b) {
        if (a < 1 || b < 1) throw new IllegalArgumentException("a or b is less than 1");
        while (b != 0) {
            int tmp = a;
            a = b;
            b = tmp % b;
        }
        return a;
    }
/**
 * Returns the greatest common divisor of the given numbers "a" and "b"
 * @param a number "a"
 * @param b number "b"
 * @return gcd(a, b)
 * @autor Thomas (www.adamjak.net)
 */
int gcd(int a, int b)
{
    if (a < 1 || b < 1)
    {
        printf("a or b is less than 1");
        return -1;
    }

    int r = 0;

    do
    {
        r = a % b;
        a = b;
        b = r;
    } while (b != 0);

    return a;
}
/**
 * Returns the greatest common divisor of the given numbers "a" and "b"
 * @param a number "a"
 * @param b number "b"
 * @return gcd(a, b)
 * @autor Thomas (www.adamjak.net)
 */
public static int gcd(int a, int b)
{
    if (a < 1 || b < 1)
    {
        throw new ArgumentException("a or b is less than 1");
    }
    int r = 0;
    do
    {
        r = a % b;
        a = b;
        b = r;
    } while (b != 0);
    return a;
}
/**
 * Returns the greatest common divisor of the given numbers "a" and "b"
 * @param $a number "a"
 * @param $b number "b"
 * @return gcd(a, b)
 * @autor Thomas (www.adamjak.net)
 */
function gcd($a, $b) {
    if ($a < 1 || $b < 1) {
        die("a or b is less than 1");
    }
    $r = 0;
    do {
        $r = $a % $b;
        $a = $b;
        $b = $r;
    } while ($b != 0);
    return $a;
}
mgcd(X, X, X).
mgcd(X, Y, X) :- Y == 0.
mgcd(X, Y, R) :- Y > X, mgcd(Y, X, R).
mgcd(X, Y, R) :- X > Y, R1 is X mod Y, mgcd(Y,R1,R).







       
 

Place for your banner

Here is the position ready for our customer's banners.