Gröttste gemeensame Deler

De gröttste gemeensame Deler is en wichtigen Begreep ut de Tallentheorie. För twee hele Tallen a un b, de nich beide liek to de 0 ween dörvt, gifft dat jümmers en gröttsten gemeensamen Deler. Dat is de gröttste natürliche Tall, de sowohl a as ok b deelt, ahn dat 'n Rest blifft.

De gröttste gemeensame Deler vun a un b warrt as $\operatorname {ggD} (a,b)$ schreven. To'n Bispeel is $\operatorname {ggD} (12,18)=6$, $\operatorname {ggD} (-4,14)=2$ un $\operatorname {ggD} (5,0)=0$.

Twee Tallen warrt relativ prim nöömt, wenn jümehr gröttste gemeensame Deler de 1 is. To'n Bispeel sünd 9 un 28 relativ prim.

In de ingelsche Literatur warrt de ggD as gcd schreven (för greatest common divisor).

De gröttste gemeensame Deler helpt bi dat Bröökreken, üm den Bröök to körten:

${42 \over 56}={3\cdot 14 \over 4\cdot 14}={3 \over 4}$

Hier hebbt wi de 14 körtt, dat is de gröttste gemeensame Deler vun 42 un 56.

Utreken vun den ggD

Utreken över de Primfaktoren

De ggD un ok dat lgV (dat lüttste gemeensame Veelfache) laat sik över de Primfaktoren vun a un b utreken. Een Bispeel:

$\operatorname {a} =3528=2^{\color {Red}3}\cdot 3^{\color {Red}2}\cdot 5^{\color {Red}0}\cdot 7^{\color {Red}2}$

$\operatorname {b} =3780=2^{\color {OliveGreen}2}\cdot 3^{\color {OliveGreen}3}\cdot 5^{\color {OliveGreen}1}\cdot 7^{\color {OliveGreen}1}$

För den $\operatorname {ggD}$ nehmt wi de lüttsten Exponenten vun de Basen:

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

För dat $\operatorname {lgV}$ nehmt wi de gröttsten Exponenten vun de Basen:

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

Utreken över den euklidschen Algorithmus

Dat Faktoriseren vun groten Tallen (dat is dat Rutfinnen vun jümehr Primfaktoren) is swoor. Denn is dat eenfacher, den $\operatorname {ggD}$ mit den euklidschen Algorithmus uttoreken, de op den greekschen Mathematiker Euklid (300 v. Chr.) trüchgeiht.

de ggD vun mehr as twee Tallen

De $\operatorname {ggD}$ lett sik ok vun mehr as twee helen Tallen utreken, wieldat de Operatschoon assoziativ is:

$\operatorname {ggD} (a,\,\operatorname {ggD} (b,c))=\operatorname {ggD} (\operatorname {ggD} (a,b),\,c)=\operatorname {ggD} (a,b,c)$

Egenschoppen

För alle helen Tallen a, b gellt:

• $\operatorname {ggD} (a,b)=\operatorname {ggD} (b,a)$ Kommutativgesetz
• $\operatorname {ggD} (-a,b)=\operatorname {ggD} (a,b)$
• $\operatorname {ggD} (a,a)=|a|$
• $\operatorname {ggD} (a,0)=|a|$
• $\operatorname {ggD} (a,1)=1$
• $\operatorname {ggD} (a,b)=\operatorname {ggD} (b,a{\bmod {b}})$
• $\operatorname {ggD} (a,b)=\operatorname {ggD} (b,a-b)$

Wenn bavento m en natürliche Tall is, denn gellt:

• $\operatorname {ggD} (ma,mb)=m\cdot \operatorname {ggD} (a,b)$ Distributivgesetz
• $\operatorname {ggD} (a+mb,b)=\operatorname {ggD} (a,b)$

Wenn m en gemeensame Deler vun a un b is, denn gellt:

• $\operatorname {ggD} (a/m,b/m)=\operatorname {ggD} (a,b)/m$