Größter gemeinsamer Teiler

Unter allen gemeinsamen Teilern zweier positiver natürlicher Zahlen mm und nn, gibt es wegen der Endlichkeit der Menge der gemeinsamen Teiler, einen größten, dieser heißt dann logischerweise größter gemeinsamer Teiler und wird mit ggT⁡\ggT abgekürzt.
Wenn zwei Zahlen nur den gemeinsamen Teiler 11 besitzen, so heißen sie teilerfremd. Es gilt dann m,nm,n teilerfremd   ⟺  ggT⁡(m,n)=1\iff \ggT(m,n)=1. Eine andere Bezeichnung für teilerfremd ist relativ prim.
Wenn man zwei natürliche Zahlen in ihre Primfaktoren zerlegt, kann man den größten gemeinsamen Teiler sofort ablesen. Es handelt sich um die Zahl, die sich durch Multiplikation der gemeinsamen Primfaktoren ergibt.
 
 

Beispiele

1) ggT⁡(4;6)=2\ggT(4;6)=2
2) ggT⁡(24;30)=6\ggT(24;30)=6, denn 24=23⋅324=2^3\cdot 3 und 30=2⋅3⋅530=2\cdot 3\cdot 5 haben die gemeinsamen Primfaktoren 22 und 33.

Euklidischer Algorithmus

Die Zerlegung einer natürlichen Zahl in Primfaktoren kann bei größeren Zahlen sehr aufwändig sein. Der Euklidische Algorithmus bietet eine Methode zur Berechnung des größten gemeinsamen Teilers, die ohne die Zerlegung in Primfaktoren auskommt. Der Algorithmus arbeitet für zwei natürliche Zahlen mm und nn wie folgt
  1. Wenn n>mn>m vertausche mm und nn
  2. Setze r=m−nr= m- n
  3. Setze m=nm=n und n=rn=r
  4. Wenn r>0r>0 gehe zu 1.
Wenn der Algorithmus bei r=0r=0 abbricht, dann ist mm der gesuchte ggT⁡\ggT.
Man kann den Algorithmus auch verfeinern, indem man im 3. Schritt rr als Rest bei der Division von mm durch nn definiert. Dadurch werden lange Subtraktionsketten vermieden.

Beispiel

Für m=30m=30 und n=24n=24 erhalten wir nach dem Euklidischen Algorithmus folgende Berechnungskette:
m n r
30 24 6
24 6 18
18 6 12
12 6 0
Der größte gemeinsame Teiler ist also 66.

Satz 5303K

Zwei positive natürliche Zahlen mm und nn sind genau dann teilerfremd, wenn es natürliche Zahlen xx und yy gibt mit xm−yn=1xm-yn=1. Formal:
ggT⁡(m;n)=1  ⟺  ∃x,y∈N:xm−yn=1\ggT(m;n)=1\iff \exists x,y\in \dom N: xm-yn=1

Satz 5303H

Wenn eine natürliche Zahl kk dass Produkt m⋅nm\cdot n teilt und zu mm teilerfremd ist, dann ist kk Teiler von nn. Formal:
k∣m⋅n∧ggT⁡(k;m)=1  ⟹  k∣nk|m\cdot n \and \ggT(k;m)=1\implies k|n

Beweis

Wenn ggT⁡(k;m)=1\ggT(k;m)=1 gibt es nach Satz 5303K natürliche Zahlen xx und yy mit kx−my=1kx-my=1. Wenn wir die Gleichung mit nn multiplizieren, ergibt sich: nkx−nmy=nnkx-nmy=n.
Nun ist sicherlich k∣nkxk|nkx und wegen der Voraussetzung ist k∣mnk|mn und damit k∣nmyk|nmy. Nach Satz 5303L gilt dann auch k∣nkx−nmyk|nkx-nmy also k∣nk|n. □\qed

Ich glaube, daß es, im strengsten Verstand, für den Menschen nur eine einzige Wissenschaft gibt, und diese ist reine Mathematik. Hierzu bedürfen wir nichts weiter als unseren Geist.

Georg Christoph Lichtenberg

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Natürliche Zahlen