6. Primzahl-Exponenten
Wir betrachten nun die Exponenten einer Primfaktorzerlegung genauer. Hierzu definieren wir:
Definition (p-Exponent, Vorkommen einer Primzahl)
Sei p eine Primzahl. Dann definieren wir die Funktion exp : ℕ* → ℕ durch:
exp(n) = „das größte e ≥ 0 derart, dass pe ein Teiler von n ist“ für alle n ≥ 1.
Ist n ≥ 1, so nennen wir exp(n) den p-Exponenten von n und sagen, dass die Primzahl p exp(n)-mal in n (als Faktor) vorkommt.
Diese Definition von exp(n) verwendet weder die Existenz noch die Eindeutigkeit einer Primfaktorzerlegung von n. Die Primzahlpotenzen
1, p, p2, p3, …, pn, …
sind unbeschränkt in den natürlichen Zahlen, sodass es ein e gibt mit den Eigenschaften:
pe teilt n, pe + 1 teilt n nicht.
Aus der Eindeutigkeit der Primfaktorzerlegung folgt:
Satz (Primfaktorzerlegung als Exponentenprodukt)
Sei n ≥ 1. Dann gilt
n = 2ex2(n) 3ex3(n) 5ex5(n) … = ∏p prim pexp(n),
wobei höchstens endlich viele Faktoren von 1 verschieden sind, sodass das Produkt als endliches Produkt geschrieben werden kann.
Beweis
Im Fall n = 1 sind alle Faktoren des Produkts gleich 1, sodass das Produkt gleich 1 ist. Sei also n ≥ 2, und sei n = p1e1 … pkek in kanonischer Primfaktorzerlegung. Dann gilt expi(n) = ei für i = 1, …, k. Denn ist i ∈ { 1, …, k }, so ist piei ein Teiler von n. Dagegen ist piei + 1 kein Teiler von n, da wir sonst eine verschiedene Primfaktorzerlegung von n konstruieren könnten. Mit dem gleichen Argument ist exp(n) = 0 für alle Primzahlen p ≠ p1, …, pk. Damit ist
n = ∏1 ≤ i ≤ k piei = ∏p prim pexp(n).
Anschaulich gesprochen gilt: Die Funktion exp liefert uns den Exponenten der Primzahl p der Primfaktorzerlegung einer natürlichen Zahl n. Dabei ist exp(n) genau dann gleich 0, wenn n nicht durch p teilbar ist.
Beispiel
Es gilt 48 = 24 · 3. Folglich ist
ex2(48) = 4, ex3(48) = 1, exp(48) = 0 für alle Primzahlen p ≥ 5.
Die Primzahl 2 kommt viermal in der Zahl 48 vor, die Primzahl 3 einmal und alle anderen Primzahlen gar nicht.
Die beiden folgenden Sätze versammeln weitere Eigenschaften der Primzahlexponenten. Sie lassen sich mit Hilfe der Eindeutigkeit der Primfaktorzerlegung leicht einsehen.
Satz (Multiplikativität von exp)
Sei p eine Primzahl. Dann gilt für alle n, m ≥ 1 und alle k ≥ 0:
exp(nm) = exp(n) + exp(m),
exp(nk) = k exp(n).
Satz (Eigenschaften von exp)
Seien n, m ≥ 1. Dann gilt:
(a) | n|m genau dann, wenn exp(n) ≤ exp(m) für alle Primzahlen p, |
(b) | ggT(n, m) = ∏p prim pmin(exp(n), exp(m)), |
(c) | kgV(n, m) = ∏p prim pmax(exp(n), exp(m)), |
(d) | n und m sind teilerfremd genau dann, wenn Für alle Primzahlen p gilt: exp(n) = 0 oder exp(m) = 0. |
Für alle natürlichen Zahlen a, b gilt max(a, b) + min(a, b) = a + b. Aus den Eigenschaften (b), (c) und der Multiplikativität gewinnen wir:
Korollar (Produktsatz für ggT und kgV)
Für alle n, m ≥ 1 gilt:
ggT(n, m) kgV(n, m) = n m für alle n, m ≥ 1.
Viele weitere Eigenschaften ließen sich anführen. Zum Beispiel gilt für alle Primzahlen p und alle n ≥ 1:
exp(n) ≠ 0 genau dann, wenn exp(n + 1) = 0.
Dies ergibt sich daraus, dass zwei aufeinanderfolgende Zahlen stets teilerfremd sind.
Die folgenden Diagramme geben einen Eindruck über den Verlauf der Exponentenfunktionen.
Die Funktion ex2 : ℕ* → ℕ
Die Funktion ex3 : ℕ* → ℕ.
Es gilt 36 = 729, sodass der Wert 6 zum ersten Mal bei 729 angenommen wird.
Die Funktion ex7 : ℕ* → ℕ.
Es gilt 74 = 2401, sodass der Wert 4 zum ersten Mal bei 2401 angenommen wird.