HCF Calculator

In mathematics, the greatest common divisor (gcd) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For example, the gcd of 8 and 12 is 4.

In the name "greatest common divisor", the adjective "greatest" may be replaced by "highest", and the word "divisor" may be replaced by "factor", so that other names include greatest common factor (gcf), etc. Historically, other names for the same concept have included greatest common measure.

The calculator above provides you with only inputs to find GCF for just two positive integers.

For example,

What is the greatest common divisor of 54 and 24?

The divisors of 54 are: 1, 2, 3, 6, 9, 18, 27, 54

The divisors of 24 are: 1, 2, 3, 4, 6, 8, 12, 24

The numbers that these two lists share in common are the common divisors of 54 and 24:

1, 2, 3, 4, 6

The greatest of these is 6. That is, the greatest common divisor of 54 and 24​

Two numbers are called relatively prime, or coprime, if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.

For example, a 24-by-60 rectangular area can be divided into a grid of: 1-by-1 squares, 2-by-2 squares, 3-by-3 squares, 4-by-4 squares, 6-by-6 squares or 12-by-12 squares. Therefore, 12 is the greatest common divisor of 24 and 60. A 24-by-60 rectangular area can thus be divided into a grid of 12-by-12 squares, with two squares along one edge (24/12 = 2) and five squares along the other (60/12 = 5).

Using Prime Factorization

In principle, greatest common divisors can be computed by determining the prime factorization of the two numbers and comparing factors, as in the following example: to compute gcd(18, 84), we find the prime factorizations 18 = 2 • 32 and 84 = 22 • 3 • 7, and since the "overlap" of the two expressions is 2 • 3, GCD (18, 84) = 6. In practice, this method is only feasible for small numbers; computing prime factorizations in general takes far too long.

Here is another concrete example, illustrated by a Venn diagram. Suppose it is desired to find the greatest common divisor of 48 and 180. First, find the prime factorizations of the two numbers:

48 = 2 × 2 × 2 × 2 × 3, 180 = 2 × 2 × 3 × 3 × 5. What they share in common is two "2"s and a "3":

• Least common multiple = 2 × 2 × ( 2 × 2 × 3 ) × 3 × 5 = 720
• Greatest common divisor = 2 × 2 × 3 = 12.

Properties

• Every common divisor of a and b is a divisor of gcd(a, b).
• gcd(a, b), where a and b are not both zero, may be defined alternatively and equivalently as the smallest positive integer d which can be written in the form d = a⋅p + b⋅q, where p and q are integers. This expression is called Bézout's identity. Numbers p and q like this can be computed with the extended Euclidean algorithm.
• gcd(a, 0) = |a|, for a ≠ 0, since any number is a divisor of 0, and the greatest divisor of a is |a|. This is usually used as the base case in the Euclidean algorithm.
• If a divides the product b⋅c, and gcd(a, b) = d, then a/d divides c.
• If m is a non-negative integer, then gcd(m⋅a, m⋅b) = m⋅gcd(a, b).
• If m is any integer, then gcd(a + m⋅b, b) = gcd(a, b).
• If m is a positive common divisor of a and b, then gcd(a/m, b/m) = gcd(a, b)/m.
• The gcd is a multiplicative function in the following sense: if a1 and a2 are relatively prime, then gcd(a1⋅a2, b) = gcd(a1, b)⋅gcd(a2, b). In particular, recalling that gcd is a positive integer valued function we obtain that gcd(a, b⋅c) = 1 if and only if gcd(a, b) = 1 and gcd(a, c) = 1.
• The gcd is a commutative function: gcd(a, b) = gcd(b, a).
• The gcd is an associative function: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c).
• If none of a1, a2, . . . , ar is zero, then gcd( a1, a2, . . . , ar ) = gcd( gcd( a1, a2, . . . , ar-1 ), ar ).
• gcd(a, b) is closely related to the least common multiple lcm(a, b): we have gcd(a, b)⋅lcm(a, b) = |a⋅b|.

This formula is often used to compute least common multiples: one first computes the gcd with Euclid's algorithm and then divides the product of the given numbers by their gcd.

• The following versions of distributivity hold true: gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c)) lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c)).
• If we have the unique prime factorizations of a = p1e1 p2e2 ⋅⋅⋅ pmem and b = p1f1 p2f2 ⋅⋅⋅ pmfm where ei ≥ 0 and fi ≥ 0, then the gcd of a and b is gcd(a,b) = p1min(e1,f1) p2min(e2,f2) ⋅⋅⋅ pmmin(em,fm).
• It is sometimes useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a complete distributive lattice with gcd as meet and lcm as join operation. This extension of the definition is also compatible with the generalization for commutative rings given below.
• In a Cartesian coordinate system, gcd(a, b) can be interpreted as the number of segments between points with integral coordinates on the straight line segment joining the points (0, 0) and (a, b).
• For non-negative integers a and b, where a and b are not both zero, provable by considering the Euclidean algorithm in base n: gcd(na − 1, nb − 1) = ngcd(a,b) − 1.