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
ggD
(
a
,
b
)
{\displaystyle \operatorname {ggD} (a,b)}
ggD
(
12
,
18
)
=
6
{\displaystyle \operatorname {ggD} (12,18)=6}
ggD
(
−
4
,
14
)
=
2
{\displaystyle \operatorname {ggD} (-4,14)=2}
ggD
(
5
,
0
)
=
0
{\displaystyle \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
56
=
3
⋅
14
4
⋅
14
=
3
4
{\displaystyle {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.
ännern
De ggD un ok dat lgV (dat lüttste gemeensame Veelfache ) laat sik över de Primfaktoren vun a un b utreken. Een Bispeel:
a
=
3528
=
2
3
⋅
3
2
⋅
5
0
⋅
7
2
{\displaystyle \operatorname {a} =3528=2^{\color {Red}3}\cdot 3^{\color {Red}2}\cdot 5^{\color {Red}0}\cdot 7^{\color {Red}2}}
b
=
3780
=
2
2
⋅
3
3
⋅
5
1
⋅
7
1
{\displaystyle \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
ggD
{\displaystyle \operatorname {ggD} }
lüttsten Exponenten vun de Basen:
ggD
(
3528
,
3780
)
=
2
2
⋅
3
2
⋅
5
0
⋅
7
1
=
252
{\displaystyle \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
lgV
{\displaystyle \operatorname {lgV} }
gröttsten Exponenten vun de Basen:
lgV
(
3528
,
3780
)
=
2
3
⋅
3
3
⋅
5
1
⋅
7
2
=
52.920
{\displaystyle \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}
ännern
Dat Faktoriseren vun groten Tallen (dat is dat Rutfinnen vun jümehr Primfaktoren) is swoor. Denn is dat eenfacher, den
ggD
{\displaystyle \operatorname {ggD} }
euklidschen Algorithmus uttoreken, de op den greekschen Mathematiker Euklid (300 v. Chr. ) trüchgeiht.
de ggD vun mehr as twee Tallen
ännern
De
ggD
{\displaystyle \operatorname {ggD} }
assoziativ is:
ggD
(
a
,
ggD
(
b
,
c
)
)
=
ggD
(
ggD
(
a
,
b
)
,
c
)
=
ggD
(
a
,
b
,
c
)
{\displaystyle \operatorname {ggD} (a,\,\operatorname {ggD} (b,c))=\operatorname {ggD} (\operatorname {ggD} (a,b),\,c)=\operatorname {ggD} (a,b,c)}
För alle helen Tallen a , b gellt:
ggD
(
a
,
b
)
=
ggD
(
b
,
a
)
{\displaystyle \operatorname {ggD} (a,b)=\operatorname {ggD} (b,a)}
Kommutativgesetz
ggD
(
−
a
,
b
)
=
ggD
(
a
,
b
)
{\displaystyle \operatorname {ggD} (-a,b)=\operatorname {ggD} (a,b)}
ggD
(
a
,
a
)
=
|
a
|
{\displaystyle \operatorname {ggD} (a,a)=|a|}
ggD
(
a
,
0
)
=
|
a
|
{\displaystyle \operatorname {ggD} (a,0)=|a|}
ggD
(
a
,
1
)
=
1
{\displaystyle \operatorname {ggD} (a,1)=1}
ggD
(
a
,
b
)
=
ggD
(
b
,
a
mod
b
)
{\displaystyle \operatorname {ggD} (a,b)=\operatorname {ggD} (b,a{\bmod {b}})}
ggD
(
a
,
b
)
=
ggD
(
b
,
a
−
b
)
{\displaystyle \operatorname {ggD} (a,b)=\operatorname {ggD} (b,a-b)}
Wenn bavento m en natürliche Tall is, denn gellt:
ggD
(
m
a
,
m
b
)
=
m
⋅
ggD
(
a
,
b
)
{\displaystyle \operatorname {ggD} (ma,mb)=m\cdot \operatorname {ggD} (a,b)}
Distributivgesetz
ggD
(
a
+
m
b
,
b
)
=
ggD
(
a
,
b
)
{\displaystyle \operatorname {ggD} (a+mb,b)=\operatorname {ggD} (a,b)}
Wenn m en gemeensame Deler vun a un b is, denn gellt:
ggD
(
a
/
m
,
b
/
m
)
=
ggD
(
a
,
b
)
/
m
{\displaystyle \operatorname {ggD} (a/m,b/m)=\operatorname {ggD} (a,b)/m}
