2.2. Primzahlen#
Mit den Teilbarkeitsregeln aus Lemma 2.1 wissen wir, dass die Zahlen \(\pm 1\) nur die beiden Teiler \(\pm 1\) besitzen. Außerdem wissen wir, dass alle ganzen Zahlen \(a \in \Z\) mit \(a \ne \pm 1\) mindestens die vier Teiler \(\pm 1,\pm a\) haben, weswegen man diese Teiler auch triviale Teiler nennt.
Unter allen ganzen Zahlen gibt es eine besondere Menge, die sich durch ihre Teilermenge auszeichnet - die sogenannten Primzahlen.
Definition 2.8 (Primzahlen)
Eine natürliche Zahl \(p\in \N, p>1\) heißt Primzahl, wenn die einzigen Teiler von \(p\) die Zahlen \(\pm 1\) und \(\pm p\) sind, d.h. wenn \(p\) nur triviale Teiler hat.
Die ersten Primzahlen sind
2.2.1. Primfaktorzerlegung#
Welche grundlegende Bedeutung die Primzahlen für die Menge der ganzen Zahlen hat zeigt das folgende zentrale Theorem der elementaren Zahlentheorie.
Satz 2.1 (Fundamentalsatz der Arithmetik)
Jede ganze Zahl \(n\ne 0\) lässt sich eindeutig (bis auf die Reihenfolge der Faktoren) schreiben als Produkt von Primzahlen in der Form
Hierbei sind \(p_1,p_2,\dots,p_r \in \N\) paarweise verschiedenen Primzahlen und die Exponenten \(e_1,e_2,\dots,e_r \in \N\) sind positive natürliche Zahlen.
Proof. Folgt in Kürze. ◻
Mit Hilfe des Fundamentalsatzes der Arithmetik lässt sich direkt eine wichtige Beobachtung ableiten, die bereits von Euklid bewiesen wurde.
Korollar 2.1 (Unendlichkeit der Primzahlen)
Es gibt unendlich viele Primzahlen.
Proof. Wir führen einen Beweis durch Widerspruch. Nehmen wir an, es gäbe nur endlich viele Primzahlen \(p_1, \ldots, p_r \in \N\). Dann kann die Zahl \(a := (p_1\cdot p_2 \cdot \ldots \cdot p_r) + 1 \in \N\) nach Annahme keine Primzahl mehr sein. Wenn \(a\) nicht prim ist muss sie nach Satz 2.1 durch mindestens eine Primzahl \(p_j, 1\leq j \leq r\) teilbar sein. Aus \(p_j \mid a\) und \(p_j \mid p_1\cdot p_2 \cdot \ldots \cdot p_r\) folgt aber schon, dass \(p_j \mid 1\) gilt. Dies ist jedoch ein Widerspruch, da die Zahl \(1\) nur triviale Teiler besitzt. Hieraus folgt schon die Behauptung des Korollars. ◻
Folgende Bemerkungen lassen sich zum Fundamentalsatz der Arithmetik festhalten.
Bemerkung 2.3 (Primfaktorzerlegungen)
Die Aussage des Fundamentalsatzes der Arithmetik heißt in der Sprache der Algebra: Der Ring der ganzen Zahlen \(\Z\) ist ein faktorieller Ring .
Gerade wenn die Primfaktorzerlegung mehrerer Zahlen gleichzeitig betrachtet oder verglichen wird, verwenden wir auch folgende Notation
\[\prod_i p_i^{e_i}\quad\text{ mit }\quad e_i\ge 0.\]Hierbei durchläuft das Produkt dann typischerweise die unendliche Menge aller Primzahlen und nur endlich viele Exponenten \(e_i\in\N_0\) von \(0\) verschieden sind. Eine verkürzte Schreibweise hierfür ist
\[\prod_p p^{e_p}.\]Trotz der Wichtigkeit der Primfaktorzerlegung natürlicher Zahlen, ist bis heute kein wirklich effizientes Verfahren zur Primfaktorzerlegung bekannt. Die Schwierigkeit, die Primfaktorzerlegung natürlicher Zahlen zu bestimmen, wird deshalb zur Konstruktion von modernen Kryptosystemen benutzt.
Wir wollen ein naives Faktorisierungsverfahren zur Bestimmung der Primfaktorzerlegung (2.1) einer natürlichen Zahl \(n \in \N\) im Folgenden diskutieren.
Algorithmus 2.1 (Naives Faktorisierungsverfahren)
Wir wollen die Primfaktorzerlegung einer natürlichen Zahl \(n\in \N\) finden und teilen rekursiv alle Primteiler \(p_i\) bzw. alle Primzahlpotenzen \(p_i^{e_i}\) heraus.
Im \(i\)-ten Schritt dieses Algorithmus haben wir folgende allgemeine Situation
wobei \(n_i \in \N\) keinen (echten) Teiler \(d_i \le p_{i-1}\) hat.
Wir starten mit \(n_1=n\).
Ist \(n_i=1\), so sind wir fertig und haben die Primfaktorzerlegung gefunden als
\[n=p_1^{e_1}\dots p_{i-1}^{e_{i-1}}.\]Sei nun \(n_i>1\) vorausgesetzt. Wir suchen nach dem kleinsten Teiler \(d_i \in \N\) von \(n_i\). Da \(n_i\) keinen Teiler \(d_i \le p_{i-1}\) hat, können wir die Suche auf \(d_i>p_{i-1}\) einschränken.
Finden wir keinen Teiler \(d_i\) mit \(p_{i-1}<d_i\le \sqrt{n_i}\), so ist \(n_i=p_i\) eine Primzahl, denn aus \(n_i=m_1m_2\) mit \(m_1,m_2>1\) folgt \(m_1\le \sqrt{n_i}\) oder \(m_2\le \sqrt{n_i}\), was nicht geht. Auch in diesem Fall haben wir eine Primfaktorzerlegung gefunden als
\[n=p_1^{e_1}\dots p_{i-1}^{e_{i-1}}p_i.\]Ist \(d_i\) der kleinste Teiler von \(n_i\) mit \(p_{i-1}<d_i\le \sqrt{n_i}\), so ist \(d_i\) eine Primzahl, also \(d_i=p_i\). Wir teilen \(p_i\) so oft wie möglich aus \(n_i\) heraus und erhalten \(n_i=p_i^{e_i}n_{i+1}\), so dass \(p_i\) die Zahl \(n_{i+1}\) nicht mehr teilt. Der kleinste Teiler von \(n_{i+1}\) ist nun größer als \(p_i\). Wir haben nun eine Primzahlpotenz faktorisiert und erhalten somit
\[n=p_1^{e_1}\dots p_i^{e_i}n_{i+1}.\]Wir wenden dieses Verfahren rekursiv auf die übrig gebliebene natürliche Zahl \(n_{i+1}\) an.
Dieses Verfahren lässt sich auch in folgendem Pseudo-Code zusammenfassen.
Eine natürliche Zahl \(n>1\) Alle Primfaktorpotenzen \(p_i^{e_i}\) der Primfaktorzerlegung von \(n\) \(e\gets 1\), \(n\gets \frac{n}{2}\) \(e\gets e+1\), \(n\gets \frac{n}{2}\) Gib \(2^e\) aus \(p\gets 3\) \(e\gets 1\), \(n\gets \frac{n}{p}\) \(e\gets e+1\), \(n\gets \frac{n}{p}\) Gib \(p^e\) aus \(p\gets p+2\) Gib \(n\) (als größten Primteiler von \(n\)) aus
Wir betrachten im Folgenden ein konkretes Beispiel zur Anwendung der naiven Faktorisierungsmethode in Algorithmus 2.1.
Beispiel 2.7 (Naives Faktorisierungsverfahren)
Wir wollen die Zahl \(n=100002\) faktorisieren, d.h. ihre Primfaktorzerlegung bestimmen.
Wir setzen zuerst \(n_1=n=100002\). Wir stellen fest, dass \(\sqrt{n_1}=316.23\dots\) ist. Wir suchen nach dem kleinsten nichttrivialen Teiler und finden sofort \(p_1=2\). Wir zerlegen also
\[n_1=2\cdot 50001\]und setzen \(n_2=50001\), da \(n_2\) offensichtlich nicht durch \(2\) teilbar ist und somit keine Potenzen dieses Teilers mehr hinzukommen.
Nun ist \(n_2=50001\) und \(\sqrt{n_2}=223.60\dots\). Wir suchen nach dem kleinsten Teiler von \(n_2\), der größer als \(2\) sein muss, und finden \(p_2=3\). Wir zerlegen also weiter rekursiv mit
\[n_2=3\cdot 16667,\]und setzen \(n_3=16667\), da \(n_3\) nicht mehr durch \(3\) teilbar ist.
Nun ist \(n_3=16667\) und \(\sqrt{16667}=129.10\dots\). Wir suchen nach dem kleinsten Teiler von \(n_3\), der größer als \(3\) sein muss, und finden \(p_3=7\). Wir zerlegen also weiter rekursiv mit
\[n_3=7\cdot 2381,\]und setzen \(n_4=2381\), da \(n_4\) nicht mehr durch \(7\) teilbar ist.
Nun ist \(n_4=2381\) und \(\sqrt{n_4}=48.79\dots\). Wir suchen nun nach einem Teiler \(d\) mit \(7<d\le 48\), finden aber keinen mehr. Daher ist \(n_4=p_4=2381\) eine Primzahl und wir können den Algorithmus terminieren.
Insgesamt erhalten wir schließlich die Primfaktorzerlegung
\[100002=2\cdot 3\cdot 7\cdot 2381.\]
Die Berechnung der Primfaktorzerlegung mit Hilfe des naiven Algorithmus 2.1 führt gerade bei großen Primfaktoren zu sehr langen Rechenzeiten, wie folgendes Beispiel zeigt.
Beispiel 2.8 (Faktorisierung großer Zahlen)
In der folgenden Tabelle findet man die Faktorisierung der Zahlen \(10^{20}+r\) mit \(1\le r\le 50\) und die benötigte Rechenzeit. Die Berechnungen wurden mit einem Computer mit Prozessor Intel Core i7-3770 CPU 3.40 GHz x 8 und Ubuntu als Betriebssystem durchgeführt.
\(n\) |
Faktorzerlegung |
Rechenzeit |
\(10^{20}+1\) |
\(73\cdot 137\cdot 1676321\cdot 5964848081\) |
0.19 sec - 0.19 s |
\(10^{20}+2\) |
\(2\cdot 3\cdot 155977777\cdot 106852828571\) |
11.55 sec - |
11.55 s |
||
\(10^{20}+3\) |
\(373\cdot 155773\cdot 1721071782307\) |
0.10 sec - 0.10 s |
\(10^{20}+4\) |
\(2^{2}\cdot 13\cdot 1597\cdot 240841\cdot 4999900001\) |
0.02 |
sec - 0.02 s |
||
\(10^{20}+5\) |
\(3\cdot 5\cdot 7^{2}\cdot 83\cdot 1663\cdot 985694468327\) |
0.07 |
sec - 0.07 s |
||
\(10^{20}+6\) |
\(2\cdot 31\cdot 6079\cdot 265323774602147\) |
1.22 sec - 1.22 s |
\(10^{20}+7\) |
\(67\cdot 166909\cdot 8942221889969\) |
0.22 sec - 0.22 s |
\(10^{20}+8\) |
\(2^{3}\cdot 3^{3}\cdot 233\cdot 1986965506278811\) |
3.23 sec - |
3.23 s |
||
\(10^{20}+9\) |
\(557\cdot 72937\cdot 2461483384901\) |
0.12 sec - 0.12 s |
\(10^{20}+10\) |
\(2\cdot 5\cdot 11\cdot 909090909090909091\) |
69.92 sec - 1 m |
9.92 s |
||
\(10^{20}+11\) |
\(3\cdot 37\cdot 467\cdot 236993\cdot 8140004071\) |
0.02 sec - |
0.02 s |
||
\(10^{20}+12\) |
\(2^{2}\cdot 7\cdot 3571428571428571429\) |
168.68 sec - 2 m |
48.68 s |
||
\(10^{20}+13\) |
\(17\cdot 1579\cdot 3917\cdot 6673\cdot 142526051\) |
0.00 |
sec - 0.00 s |
||
\(10^{20}+14\) |
\(2\cdot 3\cdot 19\cdot 877192982456140351\) |
67.90 sec - 1 m |
7.90 s |
||
\(10^{20}+15\) |
\(5\cdot 21977\cdot 910042316967739\) |
2.17 sec - 2.17 s |
\(10^{20}+16\) |
\(2^{4}\cdot 611441\cdot 10221754838161\) |
0.23 sec - 0.23 s |
\(10^{20}+17\) |
\(3^{2}\cdot 13\cdot 14071\cdot 60742012273531\) |
0.58 sec - |
0.58 s |
||
\(10^{20}+18\) |
\(2\cdot 953\cdot 33961\cdot 340267\cdot 4540219\) |
0.02 sec - |
0.02 s |
||
\(10^{20}+19\) |
\(7\cdot 14285714285714285717\) |
351.44 sec - 5 m 51.44 s |
\(10^{20}+20\) |
\(2^{2}\cdot 3\cdot 5\cdot 23\cdot 643\cdot 60689\cdot 1856948927\) |
0.00 |
sec - 0.00 s |
||
\(10^{20}+21\) |
\(11\cdot 307\cdot 29612081729345573\) |
12.77 sec - 12.77 s |
\(10^{20}+22\) |
\(2\cdot 29\cdot 298723121\cdot 5771692279\) |
21.99 sec - |
21.99 s |
||
\(10^{20}+23\) |
\(3\cdot 71^{2}\cdot 151\cdot 223\cdot 196372304837\) |
0.03 |
sec - 0.03 s |
||
\(10^{20}+24\) |
\(2^{3}\cdot 59\cdot 97\cdot 3319\cdot 19763\cdot 33298613\) |
0.00 |
sec - 0.00 s |
||
\(10^{20}+25\) |
\(5^{2}\cdot 12056437\cdot 331772977373\) |
0.92 sec - 0.92 s |
\(10^{20}+26\) |
\(2\cdot 3^{2}\cdot 7\cdot 313\cdot 2535625538820427\) |
3.76 |
sec - 3.76 s |
||
\(10^{20}+27\) |
\(6547\cdot 15274171376202841\) |
9.19 sec - 9.19 s |
\(10^{20}+28\) |
\(2^{2}\cdot 25000000000000000007\) |
473.13 sec - 7 m 53.13 s |
\(10^{20}+29\) |
\(3\cdot 47\cdot 4592117\cdot 154442898157\) |
0.32 sec - 0.32 |
s |
||
\(10^{20}+30\) |
\(2\cdot 5\cdot 13\cdot 17\cdot 43\cdot 18679\cdot 56335953419\) |
0.02 |
sec - 0.02 s |
||
\(10^{20}+31\) |
\(109\cdot 2861\cdot 320668015610119\) |
1.33 sec - 1.33 s |
\(10^{20}+32\) |
\(2^{5}\cdot 3\cdot 11\cdot 251\cdot 881\cdot 1667\cdot 1811\cdot 141851\) |
0.00 |
sec - 0.00 s |
||
\(10^{20}+33\) |
\(7\cdot 19\cdot 157\cdot 4789042670370193\) |
5.03 sec - 5.03 |
s |
||
\(10^{20}+34\) |
\(2\cdot 479\cdot 56027093\cdot 1863101011\) |
3.93 sec - 3.93 |
s |
||
\(10^{20}+35\) |
\(3^{3}\cdot 5\cdot 257\cdot 2882259691598213\) |
3.86 sec - |
3.86 s |
||
\(10^{20}+36\) |
\(2^{2}\cdot 3288757\cdot 7601656188037\) |
0.24 sec - 0.24 s |
\(10^{20}+37\) |
\(31\cdot 821\cdot 59004541\cdot 66590107\) |
4.30 sec - 4.30 s |
\(10^{20}+38\) |
\(2\cdot 3\cdot 32839\cdot 507526619771207\) |
1.66 sec - 1.66 |
s |
||
\(10^{20}+39\) |
\(100000000000000000039\) |
969.55 sec - 16 m 9.55 s |
\(10^{20}+40\) |
\(2^{3}\cdot 5\cdot 7\cdot 41\cdot 53\cdot 164354743277891\) |
0.92 |
sec - 0.92 s |
||
\(10^{20}+41\) |
\(3\cdot 2939\cdot 3313\cdot 3423400606921\) |
0.14 sec - 0.14 |
s |
||
\(10^{20}+42\) |
\(2\cdot 3119\cdot 97441\cdot 164517801499\) |
0.03 sec - 0.03 |
s |
||
\(10^{20}+43\) |
\(11\cdot 13^{2}\cdot 23\cdot 107\cdot 21857928274957\) |
0.34 |
sec - 0.34 s |
||
\(10^{20}+44\) |
\(2^{2}\cdot 3^{2}\cdot 201450463\cdot 13788887533\) |
14.80 |
sec - 14.80 s |
||
\(10^{20}+45\) |
\(5\cdot 7541\cdot 52069\cdot 50935645921\) |
0.02 sec - 0.02 s |
\(10^{20}+46\) |
\(2\cdot 288191\cdot 173496049494953\) |
0.98 sec - 0.98 s |
\(10^{20}+47\) |
\(3\cdot 7\cdot 17\cdot 4289\cdot 17321\cdot 3770533259\) |
0.00 |
sec - 0.00 s |
||
\(10^{20}+48\) |
\(2^{4}\cdot 37\cdot 61\cdot 193\cdot 199\cdot 751\cdot 96005947\) |
0.00 |
sec - 0.00 s |
||
\(10^{20}+49\) |
\(229\cdot 2017\cdot 180221\cdot 1201304833\) |
0.01 sec - 0.01 |
s |
||
\(10^{20}+50\) |
\(2\cdot 3\cdot 5^{2}\cdot 261382937\cdot 2550536291\) |
19.04 |
sec - 19.04 s |
Bemerkung 2.4 (Rechenaufwand der naiven Faktorisierung)
Der Rechenaufwand des naiven Faktorisierungsverfahrens in Algorithmus 2.1 lässt sich im schlechtesten Fall durch \(O(\sqrt{n} \cdot \ln n)\) abschätzen, da man maximal alle natürlichen Zahlen bis zu \(\sqrt{n}\) als potentielle Teiler testen muss und für jeden Teilbarkeitstest eine Division mit Rest mit einem Rechenaufwand von \(\mathcal{O}(\ln n)\) nach Bemerkung 2.2 benötigt.
Mit dem naiven Faktorisierungsverfahren kann man auch beweisen, dass eine Zahl \(n\) prim ist, indem man für jede Zahl \(a \le \sqrt{n}\) ausrechnet, dass sie kein Teiler von \(n\) ist. Die Schrittzahl für einen solchen Primzahltest wächst dann asymptotisch ebenfalls wie \(O(\sqrt{n} \cdot \ln n)\).
Bei den folgenden Zahlen \(p \in \N\), die sich als Primzahlen herausstellen, haben wir die benötigte Rechenzeit \(t\) und dann den Quotienten zwischen der Rechenzeit und der Wurzel der Primzahl \(\frac{t}{\sqrt{p}}\) dargestellt:
Primzahl \(p\) |
Rechenzeit \(t\) |
\(\frac{t}{\sqrt{p}}\) |
\(10^{13}+37\) |
0.31 sec - 0.31 s |
\(9.78\cdot 10^{-8}\) sec |
\(10^{14}+31\) |
0.72 sec - 0.72 s |
\(7.18\cdot 10^{-8}\) sec |
\(10^{15}+37\) |
2.26 sec - 2.26 s |
\(7.15\cdot 10^{-8}\) sec |
\(10^{16}+61\) |
7.14 sec - 7.14 s |
\(7.14\cdot 10^{-8}\) sec |
\(10^{17}+3\) |
22.40 sec - 22.40 s |
\(7.08\cdot 10^{-8}\) sec |
\(10^{18}+3\) |
69.19 sec - 1 m 9.19 s |
\(6.92\cdot 10^{-8}\) sec |
\(10^{19}+51\) |
287.15 sec - 4 m 47.15 s |
\(9.08\cdot 10^{-8}\) sec |
\(10^{20}+39\) |
966.80 sec - 16 m 6.80 s |
\(9.67\cdot 10^{-8}\) sec |
Extrapoliert man diese Messreihe, so braucht der Rechner mit unserem Programm zur naiven Faktorisierungsmethode mindestens \(7\cdot 10^{-8}\cdot \sqrt{p}\) Sekunden, um zu zeigen, dass \(p\) eine Primzahl ist. Mit dieser unteren Schranke lässt sich der Rechenaufwand für einige sehr große Zahlen abschätzen:
\(p\approx\) |
benötigte Bit |
Laufzeit \(\ge\) |
\(10^{20}\) |
67 |
11.66 Minuten |
\(10^{22}\) |
74 |
1.94 Stunden |
\(10^{24}\) |
80 |
19.44 Stunden |
\(10^{26}\) |
87 |
8.10 Tage |
\(10^{28}\) |
94 |
81.02 Tage |
\(10^{30}\) |
100 |
810.19 Tage |
\(10^{32}\) |
107 |
22.20 Jahre |
\(10^{34}\) |
113 |
221.97 Jahre |
\(10^{36}\) |
120 |
2219.69 Jahre |
\(10^{38}\) |
127 |
22196.85 Jahre |
\(10^{40}\) |
133 |
221968.54 Jahre |
\(10^{1234}\) |
4096 |
\(\approx 10^{602}\) Jahre |
In der letzten Zeile haben wir die typische Größe (4096 Bit) der verwendeten Primzahlen für moderne Kryptosysteme angegeben. Auch wenn es bedeutend schnellere Rechner mit paralleler Ausführung gibt, so bedeutet ein Rechenaufwand, die (mindestens) wie \(\sqrt{p}\) wächst: Zwei Dezimalstellen mehr verzehnfacht die Laufzeit. Man sieht, dass das naive Faktorisierungsverfahren schnell nicht mehr praktikabel wird, speziell wenn man bedenkt, dass das Alter unseres Universums aktuell auf ca. \(1.38 \cdot 10^{10}\) Jahre geschätzt wird.
Mit der eindeutigen Primfaktorzerlegung ganzer Zahlen erhält man eine schöne Charakterisierung der Teilbarkeitsrelation.
Satz 2.2 (Teilbarkeit via Primfaktorzerlegung)
Seien \(a,b\in\Z, a,b\ne 0\) zwei ganze Zahlen mit den jeweiligen Primfaktorzerlegungen
Dann gilt
oder in Kurzschreibweise der Primfaktorzerlegung ausgedrückt:
Proof. Wir zeigen die beiden Richtungen einzeln im Folgenden.
Hinrichtung: Wegen \(a|b\) existiert eine ganze Zahl \(c\in\Z\),
\(c\ne 0\) mit \(b = ac\). Sei \(c=\pm \prod p_i^{c_i}\) die
Primfaktorzerlegung von \(c\). Dann folgt aus \(b=ac\)
Die Eindeutigkeit der Primfaktorzerlegung liefert \(b_i=a_i+c_i\), was
wegen \(c_i\ge 0\) die Behauptung \(b_i\ge a_i\) zeigt.
Rückrichtung: Ist \(a_i\le b_i\), so ist \(b_i-a_i\ge 0\), also
\(c=\prod p_i^{b_i-a_i} = \prod p_i^{b_i} /\prod p_i^{a_i} = \frac{b}{a}\)
eine natürliche Zahl. Analog zur Hinrichtung oben sieht man \(b=\pm ac\)
und damit \(a|b\), was die Behauptung zeigt. ◻
2.2.2. Gemeinsame Teiler und ggT#
Nachdem wir uns bisher nur um die Teiler einzelner Zahlen gekümmert haben, wollen wir in diesem Abschnitt gemeinsame Teiler zweier ganzer Zahlen betrachten.
Definition 2.9 (Gemeinsame Teiler)
Seien \(m,n \in \Z\) zwei ganze Zahlen. Wir definieren die Menge der gemeinsamen Teiler \(\mathrm{gT}(m,n)\) von \(m\) und \(n\) als:
Mit Hilfe der Teilbarkeitsregeln in Lemma 2.1 sieht man sofort, dass gilt
Um dieses Konzept besser zu verstehen widmen wir uns zunächst ein paar einfachen Beispielen.
Beispiel 2.9 (Gemeinsame Teiler)
\(\mathrm{gT}(20,24) = \{\pm 1,\pm 2,\pm 4\}\),
\(\mathrm{gT}(6,0) = \{\pm 1,\pm 2,\pm 3, \pm 6\}\),
\(\mathrm{gT}(6,1)=\{\pm 1\}\).
Kennen wir die Primfaktorzerlegungen der beiden ganzen Zahlen \(a,b \in \Z\), so ist die Bestimmung der gemeinsamen Teiler mit Hilfe von Satz 2.2 ganz einfach:
Für den Spezialfall, dass mindestens eine der beiden ganzen Zahlen Null ist, gilt außerdem:
Wir wollen diesen Zusammenhang mit Hilfe eines Beispiels im Folgenden verdeutlichen.
Beispiel 2.10 (Gemeinsame Teiler via Primfaktorzerlegung)
Sei \(m=84\) und \(n=120\) mit den Primfaktorzerlegungen
Dann findet man die Menge der gemeinsamen Teiler von \(m\) und \(n\) als Menge aller möglichen Kombinationen von gemeinsamen Primfaktorpotenzen:
Die Menge \(\mathrm{gT}(m,n)\) enthält ein (bzgl. Teilbarkeit) maximales Element, das wir ohne Einschränkung mit positivem Vorzeichen wählen.
Definition 2.10 (Größter gemeinsamer Teiler)
Seien \(a,b \in \Z\) zwei ganze Zahlen mit Primfaktorzerlegung
Wir definieren den größten gemeinsamen Teiler \(\ggT(a,b)\) von \(a\) und \(b\) als
Die Idee des größten gemeinsamen Teilers ist es also die größten Primfaktorpotenzen zu selektieren, die in beiden Primfaktorzerlegungen vorkommen, und diese miteinander zu multiplizieren.
Sollte mindestens eine der beiden ganzen Zahlen \(a,b \in \Z\) Null sein, gilt folgendes für \(\ggT(a,b)\):
Wir wollen das Konzept noch einmal an einem kurzen Beispiel illustrieren.
Beispiel 2.11 (Größter gemeinsamer Teiler)
Wir betrachten wieder die natürlichen Zahlen \(m = 84\) und \(n = 120\) mit den Primfaktorzerlegungen
Der größte gemeinsame Teiler von \(m\) und \(n\) ergibt sich nun aus den gemeinsamen maximal vorkommenden Primfaktorpotenzen als:
Wir sehen also, dass \(\ggT(m,n) = 12 = \max \mathrm{gT}(m,n)\) aus Beispiel 2.10.
Das folgende Lemma charakterisiert den größten gemeinsamen Teiler noch etwas weiter.
Lemma 2.5 (Eigenschaften des \ggT)
Seien \(m,n\in\Z\) zwei ganze Zahlen. Dann hat der größte gemeinsame Teiler \(d=\ggT(m,n)\) von \(m\) und \(n\) die folgenden Eigenschaften und ist dadurch eindeutig bestimmt:
\(d\in \mathrm{gT}(m,n)\).
\(d'\in \mathrm{gT}(m,n) \Longrightarrow d'\mid d\).
\(d\ge 0\).
Proof. In den Hausaufgaben zu zeigen. ◻
Durch die ersten beiden Eigenschaften charakterisiert man einen größten gemeinsamen Teiler in der Algebra. Die dritte Eigenschaft \(d\ge 0\) dient nur der Normierung. Ohne diese wäre der größte gemeinsame Teiler \(\ggT(m,n)\) nur bis aufs Vorzeichen bestimmt.
Nun wollen wir noch eine spezielle Relation zwischen zwei ganzen Zahlen definieren, deren Menge der gemeinsamen Teiler trivial ist.
Definition 2.11 (Teilerfremdheit)
Man nennt zwei ganze Zahlen \(m,n\in\Z\) teilerfremd, wenn \(\mathrm{gT}(m,n) = \{\pm1\}\) bzw. \(\ggT(m,n)=1\) gilt.
Haben wir die jeweiligen Primfaktorzerlegungen
so gilt mit (2.2) bereits:
d.h. die Menge der Primfaktoren von \(m\) und die Menge der Primfaktoren von \(n\) sind disjunkt.
Der folgende Satz gibt noch ein paar weitere nützliche Eigenschaften an.
Satz 2.3 (Teilerfremdheit)
Für ganze Zahlen \(a,b,c \in \Z\) mit \(a,b,c\ne 0\) gilt:
\(a\mid c \ \wedge \ b\mid c\text{ und }\ggT(a,b)=1 \quad \Longrightarrow \quad ab\mid c\).
\(a\mid bc\text{ und }\ggT(a,c)=1 \quad \Longrightarrow \quad a|b\).
Ist \(d=\ggT(a,b)\) und schreibt man \(a=da'\), \(b=db'\), so gilt \(\ggT(a',b')=1\).
Proof. Folgt in Kürze. ◻
Analog zur Menge der gemeinsamen Teiler in Definition 2.9 definiert man ebenfalls die Menge der gemeinsamen Vielfachen.
Definition 2.12 (Gemeinsame Vielfache)
Für zwei ganze Zahlen \(m,n\in\Z\) definieren wir die Menge der gemeinsamen Vielfachen als
Für ganze Zahlen \(a,b \in \Z, a,b \neq 0\) ergibt sich analog eine einfache Charakterisierung durch die jeweiligen Primfaktorzerlegungen als:
Die unendliche Menge \(\mathrm{gV}(m,n)\) enthält ein bezüglich Teilbarkeit kleinstes Element, welches wir gesondert betrachen werden.
Definition 2.13 (Kleinstes gemeinsames Vielfaches)
Seien \(a,b \in \Z\) zwei ganze Zahlen. Wir definieren das kleinste gemeinsame Vielfache \(\kgV(a,b)\) von \(a\) und \(b\) als:
Die Idee ist es also für beide Zahlen jeweils die größte auftauchende Primfaktorpotenz in den jeweiligen Primfaktorzerlegungen zu selektieren.
Sollte mindestens eine der beiden ganzen Zahlen \(a,b \in \Z\) Null sein, gilt folgendes für \(\kgV(a,b)\):
Abschließend ergibt sich folgende spannende Relation zwischen dem größten gemeinsamen Teiler und dem kleinsten gemeinsamen Vielfachen zweier ganzer Zahlen \(m,n \in \Z\) durch: