Greatest Common Divisor

greatest common divisor [′grād·əst ¦käm·ən di′vīz·ər]

(mathematics)

The greatest common divisor of integersn₁,n₂, …,n_kis the largest of all integers that divide eachn_i. Abbreviated gcd. Also known as highest common factor (hcf).

---

(mathematics)

greatest common divisor - (GCD) A function that returns the largest positive integer that both arguments are integer multiples of. See also Euclid's Algorithm. Compare: lowest common multiple.

---

Greatest Common Divisor 

(of two or several natural numbers), the largest of all the common divisors of the given numbers, where a common divisor is a quantity that is a factor of each of the numbers. For example, the greatest common divisor of 45 and 72 is 9, and the greatest common divisor of 60, 84, 96, and 120 is 12.

Greatest common divisors are used to reduce fractions. The largest number that the numerator and denominator of a fraction are divisible by is the greatest common divisor of the numerator and denominator. If we know the factorizations of given numbers into prime factors, then the greatest common divisor of these numbers is obtained by multiplying the factors that occur simultaneously in all the factorizations, each factor being taken the smallest number of times that it is encountered in the factorizations. Thus, 60 = 2 . 2 . 3 . 5; 72 = 2 . 2 .2 . 3 . 3; and 252 = 2 . 2 . 3 . 3 . 7. Therefore, the greatest common divisor of 60, 72, and 252 is 2 . 2 . 3 = 12.

A common method of finding the greatest common divisor of two numbers is the method of successive division, discovered in the third century B.C. by Euclid and known as Euclid’s algorithm. It consists in dividing the larger of two given numbers by the smaller, then dividing the smaller number by the remainder from the first division, then dividing the remainder from the first division by the remainder from the second division, and so on, until a remainder equal to zero is reached. The last nonzero remainder will be the greatest common divisor of the given numbers. For example, in order to find the greatest common divisor of 3542 and 2464, we carry out the following successive divisions: 3542 = 2464 . 1 + 1078; 2464 = 1078 . 2 + 308; 1078 = 308 . 3 + 154; and 308 = 154–2. The remainder of the last division is zero, so that the greatest common divisor of 3542 and 2464 is equal to the next to last remainder, that is, 154. If the greatest common divisor of two numbers is unity, then these numbers are said to be relatively prime. The greatest common divisor d of two numbers a and b and the least common multiple m of these numbers are connected by the relationship dm = ab.

The concept of a greatest common divisor is not only applicable to numbers. For example, the greatest common divisor of two or several polynomials is the polynomial of highest degree that each of the given polynomials is divisible by. To find the greatest common divisor of polynomials, we can use methods that are completely analogous to those indicated above for numbers (in particular, Euclid’s algorithm).