Greatest common divisor

The greatest common divisor of two integers (not both zero) is the largest integer that evenly divides both numbers. It is also known as the "Greatest common factor," and abbreviated as GCD or GCF. The GCD of a and b is often written as gcd(a,b) or simply (a,b). Two numbers are called relatively prime or coprime if their greatest common divisor equals 1. For example, gcd(12,18)=6, gcd(5,0)=5, and 9 and 28 are relatively prime.

Properties

Every common divisor of a and b divides the GCD of a and b.

The greatest common divisor of a and b may be defined alternatively and equivalently as follows: it is the smallest positive integer d which can be written in the form ap+bq where p and q are integers.

If d is the GCD of a and b, and a divides the product bc, then a/d divides c.

If m is nonzero, we have gcd(ma,mb) = m gcd(a,b) and gcd(a+mb,b) = gcd(a,b). If m is a common divisor of a and b, then gcd(a/m,b/m) = gcd(a,b)/m''.

The GCD of three numbers can be computed as gcd(a,b,c) = gcd(gcd(a,b),c).

The GCD is closely related to the lowest common multiple: the product of the greatest common divisor and the lowest common multiple of two numbers is equal to the product of the original numbers.

The probability that two randomly chosen integers are relatively prime is 6/π² (see Pi).

Geometrically, gcd(a,b) is the number of points with integral coordinates on the straight line joining the points (0,0) and (a,b), excluding (0,0).

Euclid's algorithm

While the GCD of two numbers can in principle be computed by determining the prime factorizations of the two numbers and comparing factors, this is never done in practice. There is an extremely fast algorithm that determines the GCD of two integers, known as Euclid's algorithm because it is contained in Euclid's Elements. The algorithm does not require factoring:

Given the two integers a and b with b non-zero, calculate c, the remainder after the division of a by b. If c isn't zero, replace a with b, b with c, and start the process again. If c is zero, the GCD is b.

For example, the GCD of 1029 and 42 is computed by this algorithm to be 21 by following the following steps:

a	b
1029	42
42	21
21	0

For a more involved example, 46406 can be seen to have no common factors other than 1 with 36957 by the following computation:

a	b
46406	36957
36957	9449
9449	8610
8610	839
839	220
220	179
179	41
41	15
15	11
11	4
4	3
3	1
1	0

By keeping track of the quotients occurring during the algorithm, one can also determine integers p and q with ap+bq = gcd(a,b).

When analyzing the runtime of this version of Euclid's algorithm, it turns out that the inputs requiring the most steps are two successive Fibonacci numbers, and the worst case requires O(n) divisions, where n is the number of digits in the input (see Big O).

Euclid originally formulated the problem geometrically, as the problem of finding a common "measure" for two line lengths, and his algorithm proceeded by repeated subtraction of the shorter from the longer segment. This is illustrated in the following Javascript implementation which should work in most web browsers.

// get data from user and convert strings to integers

var a = parseInt(prompt("Enter value for a",0))
var b = parseInt(prompt("Enter value for b",0))


a0 = a; b0 = b;  // save original values

// the algorithm
while (a != b) { 
  if (a > b) 
	{a = a - b} 
  else  
        {b = b - a}
}

// show result
alert("The greatest common divisor of " + a0 + " and " + b0 + " is " + a)

---

/Talk