Greatest common divisor

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

It is the largest natural number by which two integers can be divided without a remainder.

The \operatorname {ggT} of two integers aand bis an integer mwith the property that it is a divisor of both aand band that any integer that also bdivides the numbers aand mis itself a divisor of For the ring \mathbb {Z} of integers (which has a total order >) one normalises the ggT \operatorname {ggT} to the largest such integer |m|.

The term "large" in \operatorname {ggT} highly correlated with the usual order relation > of integers. There is, however, an important exception: since is {\displaystyle 0}multiple of any integer m{\displaystyle 0}cannot be outdone in "size" in divisibility terms. This view is consistent with the lattice notion (and ideal theory) and simplifies some of the arithmetic rules below.

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

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

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:

  • {\displaystyle 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:

  • {\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 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:

{\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 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:

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

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

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

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

Calculation rules

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

\operatorname {ggT} (a,b)

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

(Commutative law)

{\displaystyle \operatorname {ggT} (\pm a,\pm b)}

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

{\displaystyle \operatorname {ggT} (a,a)}

{\displaystyle =|a|}

{\displaystyle \operatorname {ggT} (a,0)}

{\displaystyle =|a|}

{\displaystyle \operatorname {ggT} (a,1)}

=1

{\displaystyle \operatorname {ggT} (a,b\;{\bmod {\;}}a)}

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

{\displaystyle (a\neq 0)}

{\displaystyle \operatorname {ggT} (a,b+ac)}

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

{\displaystyle \operatorname {ggT} (a,b,c)}

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

(Associative law)

{\displaystyle \operatorname {ggT} (a\cdot c,b\cdot c)}

{\displaystyle =\operatorname {ggT} (a,b)\cdot |c|}

(Distributive law)

If is ca common divisor of aand bthen holds:
divides
cand\operatorname {ggT} (a,b){\displaystyle \operatorname {ggT} (a:c,b:c)\,=\operatorname {ggT} (a,b):|c|}

for {\displaystyle c\neq 0.}

If {\displaystyle a\equiv b\ {\bmod {\ }}c}aand bare congruent modulo c), then {\displaystyle \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 a(even 0 itself) is a divisor of 0 because {\displaystyle 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 aand bholds:

{\displaystyle \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 mand represented as a nlinear combination of mand nwith integer coefficients:

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

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

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

The coefficients sand tcan be calculated with the extended Euclidean algorithm.

Special cases

For even e, odd dand whole i,j,kholds:

{\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};

{\displaystyle \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:

{\displaystyle 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

{\displaystyle \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 aand bare associated, in characters a\sim bif 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 Ma ring R, 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 dare exactly the elements from Rthat divide all elements from M 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:

{\displaystyle {\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 Xis 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 2and 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 haveR=\mathbb {Z} [{\sqrt {-3}}]

no ggT: The elements 1+{\sqrt {-3}}and 2are 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 aand b.

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

If Ran integrality ring and the elements aand bkgV, 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 gof 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.


AlegsaOnline.com - 2020 / 2023 - License CC3