GCD

 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 two integers x, y, the greatest common divisor of x and y is denoted . For example, the GCD of 8 and 12 is 4, that is, .^[1][2]

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 highest common factor (hcf), etc.^[3][4][5][6] Historically, other names for the same concept have included greatest common measure.^[7]

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|.^[2][5] 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 positive 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). Equivalently, gcd(a mod 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 commutative function: gcd(a, b) = gcd(b, a).
• The GCD is an associative function: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c). Thus gcd(a, b, c, ...) can be used to denote the GCD of multiple arguments.
• The GCD is a multiplicative function in the following sense: if a₁ and a₂ are relatively prime, then gcd(a₁⋅a₂, b) = gcd(a₁, b)⋅gcd(a₂, b).
• 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 = p₁^e₁ p₂^e₂ ⋅⋅⋅ p_m^e_m and b = p₁^f₁ p₂^f₂ ⋅⋅⋅ p_m^f_m where e_i ≥ 0 and f_i ≥ 0, then the GCD of a and b is

  gcd(a,b) = p₁^{min(e₁,f₁)} p₂^{min(e₂,f₂)} ⋅⋅⋅ p_m^min(e_m,f_m).

• 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.^[23] 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:^[24]

  gcd(n^a − 1, n^b − 1) = n^gcd(a,b) − 1.

• An identity involving Euler's totient function:

  ${\displaystyle \gcd(a,b)=\sum _{k|a{\text{ and }}k|b}\varphi (k).}$

• ${\displaystyle \sum _{k=1}^{n}\gcd(k,n)=n\prod _{p|n}\left(1+\nu _{p}(n)\left(1-{\frac {1}{p}}\right)\right)}$ where ${\displaystyle \nu _{p}(n)}$ is the p-adic valuation.