The greatest common divisor of numbers 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 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?
Example
Find the greatest common divisor of numbers 288 and 420?
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.
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 (
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?
Příklad
Find the greatest common divisor of numbers 140 and 15?
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:
Example
Find the least common multiple of numbers 140 a 15?
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).