Greatest common divisor

The greatest common factor ( GCF ) is a mathematical term. Its counterpart is the least common multiple (LCM) . Both play a role in fractions and number theory , among other things .

It is the greatest natural number that can be used to divide two whole numbers without a remainder .

The two integers and is an integer with the property that they divider both of and by and that any integer, which is also the numbers and divides, in turn divides is. With the ring of whole numbers (which has a total order >) one normalizes the to the largest whole such number . ${\displaystyle \operatorname {ggT} }$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle m}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle m}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle \operatorname {ggT} }$ ${\displaystyle |m|}$

The term “large” in correlates to a high degree with the usual order relation > of whole numbers. There is, however, one important exception: Since the multiple of any whole number is, in questions of divisibility, “size” cannot be beaten. This view is in line with the association's conception (and ideal theory ) and simplifies some of the calculation rules listed below. ${\displaystyle \operatorname {ggT} }$ ${\displaystyle 0}$ ${\displaystyle m}$ ${\displaystyle 0}$

The English term gcd (greatest common divisor) for is also common in mathematical texts. ${\displaystyle \operatorname {ggT} }$

Often used as a shorthand for . ${\displaystyle (a,\,b)}$ ${\displaystyle \operatorname {ggT} (a,b)}$

example

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

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

calculation

Calculation using prime factorization

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

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

For the GCF one takes the prime factors that occur in both decompositions and, as the associated exponent, the respective smaller of the output exponents:

• ${\displaystyle \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 Stein's 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 complex. However, the Euclidean algorithm is an efficient method to calculate the greatest common divisor of two numbers. This method was further varied by Stein's algorithm . Whether or not this is an improvement depends on the evaluation function and "machinery" that executes the respective algorithm.

The classical Euclidean algorithm calculates the greatest common divisor by looking 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:

${\displaystyle {\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 thus 13. If you know that 13 is prime, you could already read the divisor in the example in the second step, since a prime number cannot be divided any further as a result.

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

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

So 252 is the greatest common factor between 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 GCF of several numbers

You use all the prime factors that occur in each of the numbers with the smallest power that occurs, for example:

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

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

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

so:

${\displaystyle \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.}$

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

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

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

Calculation rules

Be , , and whole numbers. Then: ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle m}$

${\displaystyle {\begin{aligned}\operatorname {ggT} (a,b)&=\operatorname {ggT} (b,a)&{\text{(Kommutativgesetz)}}\\\operatorname {ggT} (\pm a,\pm b)&=\operatorname {ggT} (a,b)\\\operatorname {ggT} (a,a)&=|a|\\\operatorname {ggT} (a,0)&=|a|\\\operatorname {ggT} (a,1)&=1\\\operatorname {ggT} (a,b\;{\bmod {\;}}a)&=\operatorname {ggT} (a,b)&(a>0)\\\operatorname {ggT} (a,b+ma)&=\operatorname {ggT} (a,b)\\\operatorname {ggT} (ma,mb)&=|m|\cdot \operatorname {ggT} (a,b)&{\text{(Distributivgesetz)}}\\\operatorname {ggT} (a,b,c)&=\operatorname {ggT} (a,\,\operatorname {ggT} (b,c))=\operatorname {ggT} (\operatorname {ggT} (a,b),\,c)&{\text{(Assoziativgesetz)}}\\\end{aligned}}}$

Here referred to the amount of . ${\displaystyle |a|}$ ${\displaystyle a}$

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

Is a common divisor of and , then: ${\displaystyle m\neq 0}$ ${\displaystyle a}$ ${\displaystyle b}$

${\displaystyle m}$   shares     and ${\displaystyle \operatorname {ggT} (a,b)}$

${\displaystyle \operatorname {ggT} (a:m,b:m)=\operatorname {ggT} (a,b):|m|}$

Is   ( and are congruent modulo ) then: ${\displaystyle a\equiv b\ {\bmod {\ }}m}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle m}$

${\displaystyle \operatorname {ggT} (a,m)=\operatorname {ggT} (b,m)}$

If you keep one of the two arguments, then gcd is a multiplicative function , because for relatively prime numbers and applies ${\displaystyle a}$ ${\displaystyle b}$

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

Lemma of Bézout

→ Main article : Bézout's lemma

After Lemma Bézout the greatest common divisor of two integers can and as a linear combination of and represent with integer coefficients: ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n}$

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

For example, the greatest common factor of and has the following representation: ${\displaystyle 12}$ ${\displaystyle 18}$

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

The coefficients and can be calculated using the extended Euclidean algorithm . ${\displaystyle s}$ ${\displaystyle t}$

special cases

The following applies to even , odd and whole : ${\displaystyle e}$ ${\displaystyle d}$ ${\displaystyle k}$

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

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

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

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

If you put a prime number together from two real summands, coprime numbers always apply to them:

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

Applications

Fractions

When truncating a fraction , a common factor is removed from the numerator and denominator of a fraction, whereby the value of the fraction does not change, e.g. B. . If you abbreviate with the greatest common divisor of the numerator and denominator, a fraction results that cannot be further reduced. For example is so ${\displaystyle {\tfrac {12}{18}}={\tfrac {6\cdot 2}{9\cdot 2}}={\tfrac {6}{9}}}$ ${\displaystyle \operatorname {ggT} (12,18)={\color {Blue}6}}$

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

A fraction that cannot be further reduced is called a reduced fraction or also completely and maximally reduced fraction .

Relationship between GCD and the least common multiple

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

Further algebraic structures with gcd

The concept of the GCD is based on the concept of divisibility as it is defined in rings. When discussing the GCD, one restricts oneself to zero divisor-free rings, in the commutative case these are the integrity rings .

An integrity ring in which two elements each have a GCD is called a GCD ring or GCD area . (In a GCB ring, every two elements also have a LCM.)

In general, such rings do not have a partial order that is antisymmetric like the whole or natural numbers have. Often the divisibility relation , which is a quasi-order, is the only order relation. Therefore, the ggT can be. no longer unambiguously normalize as non-negative, but only determine up to association . Two elements and are associated, in signs , when there is a unity with . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a\sim b}$ ${\displaystyle \epsilon }$ ${\displaystyle a=b\cdot \epsilon }$

We extend the concept of the GCD to the set of all greatest common factors of the elements of a subset of a ring , formally: ${\displaystyle M}$ ${\displaystyle R}$

${\displaystyle 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 dividers of are exactly the elements from which all elements from divide. The GCD are associated with each other. ${\displaystyle d}$ ${\displaystyle R}$ ${\displaystyle M}$

Polynomial rings

You can z. B. also form for polynomials . Instead of the prime factorization , one takes here the decomposition into irreducible factors:

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

Then

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

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

Gaussian number ring

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

Integrity rings

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

${\displaystyle a:=4=2\cdot 2=(1+{\sqrt {-3}})(1-{\sqrt {-3}}),\quad b:=(1+{\sqrt {-3}})\cdot 2}$

no gcd: the elements and are two maximum common factors , because both have the same amount , but these two elements are not associated with each other. So there is no GCF of and . ${\displaystyle 1+{\sqrt {-3}}}$ ${\displaystyle 2}$ ${\displaystyle a}$ ${\displaystyle b}$

However, the elements mentioned and have their own GCT, namely . In contrast, they have no LCM, because if one LCM would then follows from the "GCD LCM equation" that to associated needs to be. However, the common multiple is not a multiple of , so there is no LCM and the two elements have no LCM at all. ${\displaystyle 1+{\sqrt {-3}}}$ ${\displaystyle 2}$ ${\displaystyle 1}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle k:=(1+{\sqrt {-3}})\cdot 2}$ ${\displaystyle 4}$ ${\displaystyle k}$ ${\displaystyle k}$

If is an integrity ring and the elements and have a LCM, then they also have a GCF, and the equation applies ${\displaystyle R}$ ${\displaystyle a}$ ${\displaystyle b}$

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

A Euclidean ring is a main ideal ring that is a factorial ring that is ultimately a GCF ring. Likewise, every main ideal ring is a bezout ring , which in turn is always a gcd ring.

An example of a non-commutative ring GCD are the Hurwitzquaternionen .

Analytical number theory

In elementary number theory , the greatest common divisor of two whole numbers is one of the most important basic concepts. You write there regularly and mean the positive GCD, so you assume . ${\displaystyle g}$ ${\displaystyle m,n\in \mathbb {Z} \setminus \lbrace 0\rbrace }$ ${\displaystyle g=(m,n)}$ ${\displaystyle g\in \mathbb {N} }$

In analytical number theory , the gcd function can be analytically continued in a variable for a whole function . → See Ramanujan sum . ${\displaystyle \mathbb {Z} \setminus \lbrace 0\rbrace \rightarrow \mathbb {N} ;\;m\mapsto (m,n)}$ ${\displaystyle n\in \mathbb {N} \setminus \lbrace 0\rbrace }$

Individual evidence

1. ↑ Peter Bundschuh: Introduction to Number Theory . 6th edition. Springer, Berlin 2008, ISBN 978-3-540-76490-8 , p. 15.

literature

• Peter Bundschuh : Introduction to Number Theory . 6th edition. Springer, Berlin 2008, ISBN 978-3-540-76490-8 .
• Ulm University: "Elementary Number Theory" [1]

Web links

Wikibooks: Algorithm Collection - Euclidean Algorithm and GCT  - Learning and Teaching Materials

• Various online tools for prime factorization, GCF and LCM.
• Lecture notes: (PDF; 1.2 MB) Analytical continuation of the GCD to a whole function.
• Christian Spannagel : The Euclidean Algorithm . Lecture series, 2012.
• Christian Spannagel : The greatest common factor and the smallest common multiple . Lecture series, 2012.