Größter gemeinsamer Teiler

Dr grösst gmeinsami Deiler (ggT) isch e mathematische Begriff. Si Pendant isch s chliinste gmeinsame Vilfache (kgV). Beidi spiile under anderem in dr Bruchrächnig und dr Zahletheorii e Rolle.

Dr grösst gmeinsami Deiler vo zwei ganze Zahle $m$ und $n$ isch die grössti natürligi Zahl, wo me drmit $m$ und au $n$ ohni Räst cha deile. Für $m=n=0$ isch dr grösst gmeinsami Deiler nit definiert; für die algebraischi Definition gälte anderi Eigeschafte.

Die änglischi Bezeichnig gcd (greatest common divisor) für ggT isch in mathematische Text ebefalls verbreitet.

Hüfig wird au $(m,n)$ as Churzschriibwiis für $\mathrm{ggT}(m,n)$ verwändet.

Bispil

• 12 isch dur die folgende Zahle ohni Räst deilbar: 1, 2, 3, 4, 6, 12.
• 18 het die Deiler: 1, 2, 3, 6, 9, 18.

Die gmeinsame Deiler vo 12 und 18 si also 1, 2, 3, 6 und dr grösst vo dene isch 6; in Zeiche: $\mathrm{ggT}(12,18)=6$ .

Berächnig

Berächnig mit Hilf vo dr Primfaktorzerlegig

GgT und kgV cha me über d Primfaktorzerlegig vo de beide Zahle wo ge si bestimme. Bispil:

$3528=2^3\cdot 3^2\cdot 7^2$

$3780=2^2\cdot 3^3\cdot 5^1\cdot 7^1$

Für e ggT nimmt me d Primfaktore, wo in beide Zerlegige vorchömme, und as Exponänte wo drzueghöre dr jewiils chliiner vo de Usgangsexponänte:

$\mathrm{ggT}(3528,3780)=2^2\cdot 3^2\cdot 7^1=252$

Effizienz: Des Verfahre isch bsonders aifach, wenn d Primfaktorzerlegong vo de baide Zahle bekannt isch. Wenn nit, na no muas mr dia ersch berechne, zom des Verfahre ahzwende. S isch aber (no) kai schnelles Verfahre bekannt mit demm mr em Allgemaine d Primfaktorzerlegong vorre große Zahl berechne kah, wenn dia Zahl en amma Stellewertsyschtem ageah isch. Do damit isch des Verfahre im allgemeine Fall firr große Zahle et praktikabel.

Em Euklid sen Algorithmus

Mit em euklidische Algorithmus gits en effizients Verfahre, zum dr grösst gmeinsami Deiler vo zwei Zahle, welle en em Stellewertsyschtem ageah send, z berächne.

Bim euklidische Algorithmus wird schrittwiis jewiils ei Division mit Räst usgfüehrt, wobii dr Räst im neggste Schritt zum neue Divisor wird. Dr Divisor, wo kei Räst hinderloot, isch dr grösst gmeinsam Deiler vo de Usgangszahle. Bispil:

$\begin{array}{cccccc}1071& :1029& =& 1& \mathrm{Rest}& 42\\ 1029& :42& =& 24& \mathrm{Rest}& 21\\ 42& :21& =& 2& \mathrm{Rest}& 0\end{array}$

Das heisst 21 isch dr grösst gmeinsami Deiler vo 1071 und 1029.

Em Stein sen Algorithmus

Em Stein sen Algorithmus isch a Variant vom Euklidsche Algorithmus, wo bsonders gaignet isch zum de ggT vo Zahle em Binärsyschtem schnell z berechne. De Steinsche Algorithmus vermaidet allgmaine Divisione und verwendet no Divisione dur zwai. Do damit aignet er sich zom Aisatz e moderne Rechnemaschine, welle met dem Binärsyschtem schaffet.