Größter gemeinsamer Teiler

Unter allen gemeinsamen Teilern zweier positiver natürlicher Zahlen \(\displaystyle m\) und \(\displaystyle n\), 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 \(\displaystyle \ggT\) abgekürzt.
Wenn zwei Zahlen nur den gemeinsamen Teiler \(\displaystyle 1\) besitzen, so heißen sie teilerfremd. Es gilt dann \(\displaystyle m,n\) teilerfremd \(\displaystyle \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) \(\displaystyle \ggT(4;6)=2\)
2) \(\displaystyle \ggT(24;30)=6\), denn \(\displaystyle 24=2^3\cdot 3\) und \(\displaystyle 30=2\cdot 3\cdot 5\) haben die gemeinsamen Primfaktoren \(\displaystyle 2\) und \(\displaystyle 3\).

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 \(\displaystyle m\) und \(\displaystyle n\) wie folgt
  1. Wenn \(\displaystyle n>m\) vertausche \(\displaystyle m\) und \(\displaystyle n\)
  2. Setze \(\displaystyle r= m- n\)
  3. Setze \(\displaystyle m=n\) und \(\displaystyle n=r\)
  4. Wenn \(\displaystyle r>0\) gehe zu 1.
Wenn der Algorithmus bei \(\displaystyle r=0\) abbricht, dann ist \(\displaystyle m\) der gesuchte \(\displaystyle \ggT\).
Man kann den Algorithmus auch verfeinern, indem man im 3. Schritt \(\displaystyle r\) als Rest bei der Division von \(\displaystyle m\) durch \(\displaystyle n\) definiert. Dadurch werden lange Subtraktionsketten vermieden.

Beispiel

Für \(\displaystyle m=30\) und \(\displaystyle n=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 \(\displaystyle 6\).

Satz 5303K

Zwei positive natürliche Zahlen \(\displaystyle m\) und \(\displaystyle n\) sind genau dann teilerfremd, wenn es natürliche Zahlen \(\displaystyle x\) und \(\displaystyle y\) gibt mit \(\displaystyle xm-yn=1\). Formal:
\(\displaystyle \ggT(m;n)=1\iff \exists x,y\in \dom N: xm-yn=1\)

Satz 5303H

Wenn eine natürliche Zahl \(\displaystyle k\) dass Produkt \(\displaystyle m\cdot n\) teilt und zu \(\displaystyle m\) teilerfremd ist, dann ist \(\displaystyle k\) Teiler von \(\displaystyle n\). Formal:
\(\displaystyle k|m\cdot n \and \ggT(k;m)=1\implies k|n\)

Beweis

Wenn \(\displaystyle \ggT(k;m)=1\) gibt es nach Satz 5303K natürliche Zahlen \(\displaystyle x\) und \(\displaystyle y\) mit \(\displaystyle kx-my=1\). Wenn wir die Gleichung mit \(\displaystyle n\) multiplizieren, ergibt sich: \(\displaystyle nkx-nmy=n\).
Nun ist sicherlich \(\displaystyle k|nkx\) und wegen der Voraussetzung ist \(\displaystyle k|mn\) und damit \(\displaystyle k|nmy\). Nach Satz 5303L gilt dann auch \(\displaystyle k|nkx-nmy\) also \(\displaystyle k|n\). \(\displaystyle \qed\)

Seit der Zeit der Griechen bedeutet "Mathematik" zu sagen, "Beweis" zu sagen.

N. Bourbaki

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е