Theorie:
ggT
Beim Kürzen von Brüchen macht man nichts anderes, als durch einen gemeinsamen Teiler von Zähler und Nenner zu kürzen. Kürzt man durch den größten gemeinsamen Teiler, so erhält man einen nicht mehr vereinfachbaren Bruch - Zähler und Nenner sind teilerfremd. Den größten gemeinsamen Teiler kürzt man oft als "ggT" ab.
Seien \(n,m\in\mathbb N\). Dann ist der größte gemeinsame Teiler von \(m\) und \(n\) das größte \(d\in\mathbb N\) mit \(d\ge 1\), sodass \(d|m\) und \(d|n\). Man bezeichnet ihn mit \(\text{ggT}(m,n)\).
Das Bestimmen des ggT ist, anders als das Finden von Teilern einer Zahl, einfach und schnell durchführbar. Ein Verfahren, den ggT von zwei natürlichen Zahlen zu bestimmen, ist der Euklidsche Algorithmus. Die Grundidee ist, dass \(d\) ein Teiler von \(m\) und \(n\) ist genau dann, wenn \(d\) ein Teiler von \(n\) und \(m-n\) (nimm an, dass \(m>n\)).
Euklidscher Algorithmus für \(m>n\):
- Bestimme den Rest der Division \(m:n\), nenne ihn \(n_1\), und definiere \(m_1:=n\).
- Bestimme den Rest der Division \(m_1:n_1\), und nenne ihn \(n_2\). Definiere \(m_2:=n_1\).
- Bestimme den Rest der Division \(m_2:n_2\), usw.
- Wiederhole das so lange, bis bei der Divison von \(m_i:n_i\) kein Rest mehr bleibt. Dieses \(n_i\) ist der ggT.
Gilt für zwei Zahlen \(\text{ggT}(m,n)=1\), so nennt man sie teilerfremd - sie besitzen dann außer \(1\) keinen gemeinsamen Teiler.
Beispiel:
Bestimmen wir \(\text{ggT}(4056,3780)\).
- \(m=4056\) und \(n=3780\). Die Division \(m:n\) hat den Rest \(276\). Also definieren wir \(m_1=3780\) und \(n_1=276\).
- Bei der Division \(m_1:n_1\) bleibt der Rest \(192\). Wir definieren nun \(m_2= 276\) und \(n_2 = 192\).
- Bei der Division \(m_2:n_2\) erhalten wir den Rest \(84\). Wir definieren also \(m_3 = 192\) und \(n_3 = 84\).
- Die Division \(m_3:n_3\) hat den Rest \(24\). Wir definieren \(m_4 = 84\) und \(n_4=24\).
- Bei der Division \(m_4:n_4\) bleibt der Rest \(12\). Wir definieren \(m_5=24\) und \(n_5=12\).
- Bei der Division \(m_5:n_5\) bleibt kein Rest, \(m_5\) ist durch \(n_5\) teilbar. Damit ist \(n_5=12\) der gesuchte ggT!
Also ist \(\text{ggT}(4056,3780)=12\).
kgV
Eng verwandt mit dem ggT ist das kleinste gemeinsame Vielfache, oft mit "kgV" abgekürzt.
Seien \(m,n\in\mathbb N\). Das kleinste gemeinsame Vielfache von \(m\) und \(n\), bezeichnet mit \(\text{kgV}(m,n)\), ist die kleinste natürliche Zahl \(k>0\), sodass \(m|k\) und \(n|k\).
Schreibt man \(m=m'\cdot d\) und \(n=n'\cdot d\), wobei \(d=\text{ggT}(m,n)\) ist und \(m',n'\in \mathbb N\) entsprechend, so ist \(\text{ggT}(m',n')=1\). Sei \(k=\text{kgV}(m,n)\). Da einerseits \(m|k\), muss \(k=m'\cdot d\cdot k'\) gelten, mit einem vorerst unbekannten \(k'\in\mathbb N\). Andererseits soll auch \(n|k\) gelten. Der Faktor \(d\) kommt in \(k\) bereits vor, es "fehlt" nur mehr \(n'\). Also ist \(k=m'\cdot n'\cdot d\).
Es gilt für \(m,n\ge 1\):
\(\displaystyle \text{kgV}(m,n)=\frac {m\cdot n}{\text{ggT}(m,n)}\) .
Das kleinste gemeinsame Vielfache kommt bei der Bruchrechnung vor: Bringt man zwei Brüche auf einen gemeinsamen Nenner, so ist der kleinstmögliche gemeinsame Nenner gleich dem \(\text{kgV}\) der beiden Nenner.
Das Produkt zweier Zahlen ist immer ein gemeinsames Vielfaches, aber nur für zwei teilerfremde Zahlen ist es auch gleich dem kleinsten gemeinsamen Vielfachen.