Greatest common divisor (gcd)

The greatest common divisor (gcd) of integers is the largest integer dividing them both. This article explains its definition, properties, computation (Euclidean algorithm) and common uses.

Author: Leandro Alegsa Created: November 13, 2022 Updated: June 27, 2026

Definition and basic properties

The greatest common divisor, written gcd(a, b), of two integers a and b is the largest positive integer that divides both a and b without leaving a remainder. The notion applies to any pair or finite set of integers. For nonzero integers, gcd(0, n) equals |n|. Many texts adopt the convention gcd(0, 0) = 0, though some leave that case undefined. The term "highest common factor" (HCF) is also used in older elementary texts.

$\gcd(x,y)$

Image gallery

1 Image

en.wikipedia.org · Public domain

Characterizations

There are several equivalent ways to describe gcd(a, b): it is the greatest positive divisor common to a and b; it can be obtained from prime factorizations as the product of each common prime raised to the minimum exponent; and it is the smallest positive integer that can be written as an integer linear combination ax + by. That last statement is fundamental: the extended Euclidean algorithm produces integers x and y with ax + by = gcd(a, b).

Important properties

Multiplicative relation with least common multiple: gcd(a, b) × lcm(a, b) = |a × b| for nonzero integers.
Associativity and commutativity: gcd(a, b) = gcd(b, a), and gcd(a, gcd(b, c)) = gcd(gcd(a, b), c).
If d = gcd(a, b) then gcd(a/d, b/d) = 1; a and b are called relatively prime when their gcd is 1.

Computation and algorithms

The standard practical method to compute gcd(a, b) is the Euclidean algorithm, attributed to Euclid. It repeatedly replaces the larger number by its remainder on division by the smaller number until a remainder of zero appears; the last nonzero remainder is the gcd. The extended Euclidean algorithm carries the same steps while also producing coefficients x and y with ax + by = gcd(a, b). These algorithms are fast and underpin many computational tasks, including modular inverses used in public-key cryptography.

Uses, examples and generalizations

Gcds are used to reduce fractions to lowest terms, to detect coprimality, and to solve linear Diophantine equations. Example: gcd(48, 18) = 6, since 48 = 6×8 and 18 = 6×3; applying the Euclidean algorithm yields 48 = 18×2 + 12, 18 = 12×1 + 6, 12 = 6×2 + 0. The concept extends beyond integers: one can define greatest common divisors in more general rings, though existence and uniqueness may require additional conditions.

Notable facts

Many elementary number-theory results involve the gcd: the fundamental theorem of arithmetic supports the prime-exponent description, and the linear-combination property links gcds to modules and ideals in algebra. For practical computations and proofs, the Euclidean algorithm remains the most important tool. For further reading on basic definitions and examples, see the article on integers.

Example

12 is divisible by the following numbers without remainder: 1, 2, 3, 4, 6, 12.
18 has these divisors: 1, 2, 3, 6, 9, 18.
So the common divisors of 12 and 18 are 1, 2, 3, 6 and the largest of these is 6; in characters:

$\operatorname {ggT} (12,18)=6$

Calculation

Calculation via prime factorisation

GgT and kgV can be determined by the prime factorization of the two given numbers. Example:

$3528=2^{\color {Red}3}\cdot 3^{\color {Red}2}\cdot 5^{\color {Red}0}\cdot 7^{\color {Red}2}$
$3780=2^{\color {OliveGreen}2}\cdot 3^{\color {OliveGreen}3}\cdot 5^{\color {OliveGreen}1}\cdot 7^{\color {OliveGreen}1}$

For the ggT, one takes the prime factors that occur in both decompositions and the smaller of the initial exponents as the associated exponents:

$\operatorname {ggT} (3528,3780)=2^{\color {OliveGreen}2}\cdot 3^{\color {Red}2}\cdot 5^{\color {Red}0}\cdot 7^{\color {OliveGreen}1}=252$

Euclidean and Stone Algorithm

The calculation of the prime factorization of large numbers and thus also the determination of the greatest common divisor according to the above method is very time-consuming. With the Euclideanalgorithm, however, there is an efficient method for calculating the greatest common divisor of two numbers. This method was further varied by Stein's algorithm. Whether this is an improvement depends on the respective evaluation function and "machinery" that executes the respective algorithm.

The classical Euclidean algorithm calculates the greatest common divisor by searching for a common "measure" for the lengths of two lines. To do this, the smaller of two lengths is subtracted from the larger and this step is repeated with the result and the smaller length until the subtracted number is identical to the result. Example:

${\begin{aligned}143-65&=78\\78-65&=13\\65-13&=52\\52-13&=39\\39-13&=26\\26-13&=13\\\end{aligned}}$

The greatest common divisor is therefore 13. If you know that 13 is prime, you could already read off the divisor in the second step in the example, since a prime number cannot be divided further as a result.

In the modern Euclidean algorithm, a division with remainder is carried out in successive steps, whereby the remainder becomes the new divisor in the next step. The divisor with a remainder of 0 is the greatest common divisor of the original numbers. Example:

${\begin{aligned}3780&:3528&=\ &1&\ \operatorname {Rest} &\ 252\\3528&:252&=\ &14&\ \operatorname {Rest} &\ 0\\\end{aligned}}$

Thus 252 is the greatest common divisor of 3780 and 3528.

In C, the algorithm is formulated as follows:

int GreatestCommonDivisor(int a, int b) { int h; if (a == 0) return abs(b); if (b == 0) return abs(a); do { h = a % b; a = b; b = h; } while (b != 0); return abs(a); }

The ggT of several numbers

One uses all prime factors that occur in each of the numbers with the smallest occurring power in each case, for example:

$144=2^{\color {Red}4}\cdot 3^{\color {Red}2}\cdot 5^{\color {Red}0}\cdot 7^{\color {Red}0}$

$160=2^{\color {OliveGreen}5}\cdot 3^{\color {OliveGreen}0}\cdot 5^{\color {OliveGreen}1}\cdot 7^{\color {OliveGreen}0}$

$175=2^{\color {Blue}0}\cdot 3^{\color {Blue}0}\cdot 5^{\color {Blue}2}\cdot 7^{\color {Blue}1},$

so:

$\operatorname {ggT} (144,160,175)=2^{\color {Blue}0}\cdot 3^{\color {OliveGreen}0}\cdot 5^{\color {Red}0}\cdot 7^{\color {Red}0}=1.$

One could also first calculate $\operatorname {ggT} (144,160)=16$ and then calculate $\operatorname {ggT} (16,175)=1,$ because as a two-digit link on the natural numbers, the ggT is associative:

$\operatorname {ggT} (m,\,\operatorname {ggT} (n,o))=\operatorname {ggT} (\operatorname {ggT} (m,n),\,o).$

This justifies the notation $\operatorname {ggT} (m,n,o)$ .

Calculation rules

For integers a,b,c holds - with |a| as the magnitude of :

●	$\operatorname {ggT} (a,b)$	$=\operatorname {ggT} (b,a)$	(Commutative law)
●	$\operatorname {ggT} (\pm a,\pm b)$	$=\operatorname {ggT} (a,b)$
●	$\operatorname {ggT} (a,a)$	$=\|a\|$
●	$\operatorname {ggT} (a,0)$	$=\|a\|$
●	$\operatorname {ggT} (a,1)$
●	$\operatorname {ggT} (a,b\;{\bmod {\;}}a)$	$=\operatorname {ggT} (a,b)$	$(a\neq 0)$
●	$\operatorname {ggT} (a,b+ac)$	$=\operatorname {ggT} (a,b)$
●	$\operatorname {ggT} (a,b,c)$	$=\operatorname {ggT} (a,\,\operatorname {ggT} (b,c))=\operatorname {ggT} (\operatorname {ggT} (a,b),\,c)$	(Associative law)
●	$\operatorname {ggT} (a\cdot c,b\cdot c)$	$=\operatorname {ggT} (a,b)\cdot \|c\|$	(Distributive law)
●	If is a common divisor of and then holds: dividesand $\operatorname {ggT} (a,b)$ $\operatorname {ggT} (a:c,b:c)\,=\operatorname {ggT} (a,b):\|c\|$		for $c\neq 0.$
●	If $a\equiv b\ {\bmod {\ }}c$ and are congruent modulo ), then $\operatorname {ggT} (a,c)\qquad \;\;\,=\operatorname {ggT} (b,c)$

From the mentioned calculation rule $\operatorname {ggT} (a,0)=|a|$ results specifically in $\operatorname {ggT} (0,0)=0$ . This also follows from the fact that every integer (even 0 itself) is a divisor of 0 because $a\cdot 0=0$ , while conversely 0 does not divide any number different from 0.

If one of the two arguments is kept fixed, then $\operatorname {ggT}$ a multiplicative function, because for divisor alien numbers and holds:

$\operatorname {ggT} (ab,c)=\operatorname {ggT} (a,c)\cdot \operatorname {ggT} (b,c)$

Bézout lemma

→ Main article: Bézout lemma

According to Bézout's lemma, the greatest common divisor of two integers and represented as a linear combination of and with integer coefficients:

$\operatorname {ggT} (m,n)=s\cdot m+t\cdot n$ with $s,t\in \mathbb {Z}$

For example, the greatest common divisor of and has the following representation:

$\operatorname {ggT} (12,18)=6=(-1)\cdot 12+1\cdot 18$

The coefficients and can be calculated with the extended Euclidean algorithm.

Special cases

For even , odd and whole i,j,k holds:

$\operatorname {ggT} (2e,e^{2}-1)=1$ ;

$\operatorname {ggT} (2d,d^{2}-1)=2$ ;

$\operatorname {ggT} (2k(k+1),2k+1)=1$ ;

$\operatorname {ggT} (4k,4k^{2}-1)=1$ ;

$\operatorname {ggT} (i-j,1+i+j)=\operatorname {ggT} (1+2j,1+2i)$ ;

$\operatorname {ggT}(a,b)=2\operatorname {ggT}(a/2,b/2)$ if a and b are even.

$\operatorname {ggT}(a,b)=\operatorname {ggT}(a/2,b)$ if a is even and b is odd.

$\operatorname {ggT}(a,b)=\operatorname {ggT}((a-b)/2,b)$ if a and b are odd.

If a prime number is composed of two real summands, it is always alien to the divisor:

$p=a+b;0<b\leq a<p;a,b\in \mathbb {N} ,p\in \mathbb {P} ;ggT(a,b)=1$ .

Applications

Fractions

Reducing removes a common factor of the numerator and denominator of a fraction, but does not change the value of the fraction, e.g. ${\tfrac {12}{18}}={\tfrac {6\cdot 2}{9\cdot 2}}={\tfrac {6}{9}}$ . If you shorten with the greatest common divisor of the numerator and denominator, you get a fraction that cannot be shortened any further. For example, $\operatorname {ggT} (12,18)={\color {Blue}6}$ , so

${\frac {12}{18}}={\frac {2\cdot {\color {Blue}6}}{3\cdot {\color {Blue}6}}}={\frac {2}{3}}$

A fraction that cannot be shortened further is called a truncated fraction or a fully and maximally truncated fraction.

Relationship between ggT and the least common multiple

$\mathrm {ggT} (a,b)\cdot \mathrm {kgV} (a,b)=a\cdot b$

Other algebraic structures with ggT

The concept of the ggT builds on the concept of divisibility as defined in rings. In the discussion of the ggT, one restricts oneself to zero-divisible rings, in the commutative case these are the integrity rings.

An integrity ring in which every two elements have a ggT is called a ggT ring or ggT range. (In a ggT ring, every two elements also have a kgV).

In general, such rings do not have a half-order, which is antisymmetrical, as the integers or the natural numbers have one. Often the divisibility relation, which is a quasi-order, is the only order relation. Therefore, the ggT can no longer be uniquely normalised as non-negative, but can only be determined down to associativity. Two elements and are associated, in characters $a\sim b$ if there is a unit $\epsilon$ with $a=b\cdot \epsilon$

We extend the notion of ggT to the set of all greatest common divisors of the elements of a subset a ring , formally:

$d\in \operatorname {ggT} (M)\quad :\Longleftrightarrow \quad \forall y\in R:(\forall x\in M:y\mid x)\Leftrightarrow y\mid d$ .

In words: The divisors of are exactly the elements from that divide all elements from The ggT are associated with each other.

Polynomial rings

You can also form the ggT for polynomials, for example. Instead of the prime factorization, the decomposition into irreducible factors is used here:

${\begin{aligned}f(X,Y)&=X^{2}+2XY+Y^{2}=(X+Y)^{2}\\g(X,Y)&=X^{2}-Y^{2}=(X+Y)(X-Y)\end{aligned}}$

Then

$\operatorname {ggT} (f,g)\sim X+Y$

The polynomial ring $\mathbb {Q} [X]$ in a variable is Euclidean. There, to calculate the $\operatorname {ggT}$ a division with remainder.

Gaussian number ring

In the Gaussian number ring $\mathbb {Z} +\mathrm {i} \mathbb {Z}$ is the greatest common divisor of and $1+3\mathrm {i}$ even $1+\mathrm {i}$ because $2=-\mathrm {i} (1+\mathrm {i} )^{2}$ and $1+3\mathrm {i} =(1+\mathrm {i} )(2+\mathrm {i} )$ . Strictly speaking, is $1+\mathrm {i}$ only a greatest common divisor, since all numbers associated with this number are also greatest common divisors. (The units are . $\pm 1,\pm \mathrm {i}$ )

Integrity rings

In the integrity ring the elements have $R=\mathbb {Z} [{\sqrt {-3}}]$

no ggT: The elements $1+{\sqrt {-3}}$ and are two maximum common divisors, because both have the same magnitude, but these two elements are not associated with each other. So there is no ggT of and .

The elements $1+{\sqrt {-3}}$ and have a ggT, namely . On the other hand, they have no kgV, because if were a kgV, then it follows from the "ggT-kgV equation" that must be associated to However, the common multiple is not a multiple of so is not a kgV and the two elements have no kgV at all.

If an integrality ring and the elements and kgV, then they also have a ggT, and the equation applies

$a\cdot b\sim \operatorname {ggT} (a,b)\cdot \operatorname {kgV} (a,b)$

A Euclidean ring is a principal ideal ring, which is a factorial ring, which is ultimately a ggT ring. Likewise, every principal ideal ring is a Bézout ring, which in turn is always a ggT ring.

An example of a non-commutative ggT ring are the Hurwitz quaternions.

Analytic Number Theory

In elementary number theory, the greatest common divisor of two integers $m,n\in \mathbb {Z} \setminus \lbrace 0\rbrace$ to the most important basic concepts. There, one regularly writes g= g=(m,n) and then means the positive ggT, thus assumes $g\in \mathbb {N}$ .

In analytic number theory, the ggT function $\mathbb {Z} \setminus \lbrace 0\rbrace \rightarrow \mathbb {N} ;\;m\mapsto (m,n)$ in one variable for fixed be $n\in \mathbb {N} \setminus \lbrace 0\rbrace$ analytically continued to an entire function. → See Ramanujan sum.

Author

AlegsaOnline.com Greatest common divisor (gcd) Leandro Alegsa

URL: https://en.alegsaonline.com/art/40610

How to cite this article

APA

Alegsa, L. (June 27, 2026). Greatest common divisor (gcd). AlegsaOnline.com. https://en.alegsaonline.com/art/40610

MLA

Alegsa, Leandro. “Greatest common divisor (gcd).” AlegsaOnline.com, June 27, 2026, https://en.alegsaonline.com/art/40610

Chicago

Alegsa, Leandro. “Greatest common divisor (gcd).” AlegsaOnline.com. Updated June 27, 2026. https://en.alegsaonline.com/art/40610

BibTeX

@misc{alegsaonline_40610,
  author = {Alegsa, Leandro},
  title = {Greatest common divisor (gcd)},
  year = {2026},
  howpublished = {AlegsaOnline.com},
  url = {https://en.alegsaonline.com/art/40610},
  note = {Updated: June 27, 2026; Language: en}
}

TXT

Leandro Alegsa. “Greatest common divisor (gcd).” AlegsaOnline.com. Updated: June 27, 2026. https://en.alegsaonline.com/art/40610