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.