Greatest common divisor

Author: Leandro Alegsa Creation date: November 13, 2022

The greatest common divisor (gcd) or highest common factor (HCF) of two integers x and y, usually written as $\gcd(x,y)$ , is the greatest (largest) number that divides both of the integers evenly. GCDs are useful in simplifying fractions to the lowest terms. Euclid came up with the idea of GCDs.

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.