§ 6. Die Primfaktorzerlegung

\underline{(6.1)} Der HAUPTSATZ der elementaren Zahlentheorie

Jede natürliche Zahl n ≥ 2 läßt sich als ein Produkt von endlich vielen Primzahlen darstellen.

Diese Produktdarstellung ist eindeutig bis auf die Reihenfolge der Faktoren.

\underline{(6.2) KOROLLAR:} Jede natürliche Zahl n ≥ 2 läßt sich auf genau eine Weise darstellen in der Form

(⋆) n = p_{1}^{k_{1}} · p_{2}^{k_{2}} · . . . · p_{r}^{k_{r}} = ∏_{i=1}^{r} p_{i}^{k_{i}}

mit r ∈ ℕ , p_{i} ∈ IP und k_{i} ∈ ℕ für alle i = 1, 2, …, r und p_{1} < p_{2} < … < p_{r} .

(⋆) heißt die kanonische PFZ von n.

\underline{(6.3) BEM:} a) Für n ∈ ℕ bezeichne

T_{IP}(n) := T (n) ∩ IP

die Menge aller Primteiler von n.

b) Besitzt n ∈ ℕ die kanonische PFZ n = p_{1}^{k_{1}} · p_{2}^{k_{2}} · . . . · p_{r}^{k_{r}} , so gilt

T_{IP}(n) = {p_{1}, p_{2}, …, p_{r}} .

c) In manchen Fällen ist es günstiger, auch den Exponenten 0 in der PFZ einer Zahl zuzulassen:

25 = 2^{0} · 5^{2} · 7^{0}

Dies ist aber nicht mehr die kanonische PFZ von 25 , da 2 |̸ 25 und 7 |̸ 25 .

Die positiven Teiler einer natürlichen Zahl

\underline{Beispiel:} Die positiven Teiler von 72 = 2^{3} · 3^{2}

\begin{matrix}k & l & 2^{k} · 3^{l} & t \\ 0 & 0 & 2^{0} · 3^{0} & 1 \\ 1 & 0 & 2^{1} · 3^{0} & 2 \\ 2 & 0 & 2^{2} · 3^{0} & 4 \\ 3 & 0 & 2^{3} · 3^{0} & 8 \\ 0 & 1 & 2^{0} · 3^{1} & 3 \\ 1 & 1 & 2^{1} · 3^{1} & 6 \\ 2 & 1 & 2^{2} · 3^{1} & 12 \\ 3 & 1 & 2^{3} · 3^{1} & 24 \\ 0 & 2 & 2^{0} · 3^{2} & 9 \\ 1 & 2 & 2^{1} · 3^{2} & 18 \\ 2 & 2 & 2^{2} · 3^{2} & 36 \\ 3 & 2 & 2^{3} · 3^{2} & 72 \end{matrix}

\underline{(6.4) SATZ:} Besitzt die natürliche Zahl n ∈ ℕ eine Darstellung der Form

n = p_{1}^{k_{1}} · p_{2}^{k_{2}} · . . . · p_{s}^{k_{s}}

mit paarweise verschiedenen Primzahlen p_{1}, p_{2}, …, p_{s} und Exponenten k_{i} ≥ 0, so sind für t ∈ ℕ folgende Aussagen quivalent:

a) t | n

b) Es gibt Zahlen l_{i} ∈ ℕ_{0} mit 0 ≤ l_{i} ≤ k_{i} für alle i = 1, 2, …, s und

t = p_{1}^{l_{1}} · p_{2}^{l_{2}} · . . . · p_{s}^{l_{s}}

\underline{(6.5) KOROLLAR:} Besitzt die natürliche Zahl n ∈ ℕ eine Darstellung der Form

n = ∏_{i=1}^{s} p_{i}^{k_{i}}

mit paarweise verschiedenen Primzahlen p_{1}, p_{2}, …, p_{s} und Exponenten k_{i} ≥ 0, so gilt

τ(n) = ∏_{i=1}^{s} (k_{i} + 1)

\underline{BEM:} Die Anzahl der Teiler einer natürlichen Zahl n hängt nicht von der Größe dieser Zahl ab, sondern von der Häufigkeit der Primteiler. So haben z.B. die Zahlen

72 = 2^{3} · 3^{2} und 1 048 929 872 381 = 101^{3} · 1009^{2} (13 Stellen)

diegleiche Anzahl positiver Teiler, nämlich 12 .

\underline{(6.6) SATZ:} Für die Teileranzahlfunktion τ : ℕ ⟶ ℕ gilt:

a) τ(1) = 1 b) τ(p^{k}) = k + 1 für alle p ∈ IP, k ∈ ℕ

c) Für \underline{teilerfremde} natürliche Zahlen m und n gilt τ(m·n) = τ(m)·τ(n) . (Diese Bedingung bedeutet, daß τ multiplikativ ist.)

\underline{BEM:} Durch die drei Eigenschaften aus (6.6) ist die Teileranzahlfunktion τ vollständig bestimmt.

Berechnungsmethode für ggT und kgV

\underline{(6.7) SATZ:} Seien m, n ∈ ℕ. Dann gibt es paarweise verschiedene Primzahlen p_{1}, p_{2}, …, p_{t} und Zahlen k_{1}, k_{2}, …, k_{t}, l_{1}, l_{2}, …, l_{t} ∈ ℕ_{0} mit folgenden Eigenschaften:

a) m = ∏_{i=1}^{t} p_{i}^{k_{i}} , n = ∏_{i=1}^{t} p_{i}^{l_{i}}

b) ggT(m, n) = ∏_{i=1}^{t} p_{i}^{min(k_{i},l_{i})} c) kgV(m, n) = ∏_{i=1}^{t} p_{i}^{max(k_{i},l_{i})}

\underline{(6.8) KOROLLAR:} Für alle m, n ∈ ℕ gilt ggT(m, n) · kgV(m, n) = m · n.

Berechnung der PFZ einer natürlichen Zahl

Problem 1 : Wie läßt sich die PFZ einer natürlichen Zahl n ≥ 2 bestimmen ? Problem 2 : Wie kann man einen nichttrivialen Teiler einer ungeraden Zahl n ≥ 3 finden ?

(6.9) Methode der sukzessiven Divisionen Sei n ≥ 3 eine ungerade natürliche Zahl. (u_{k})_{k∈ℕ} sei eine streng monoton wachsende Folge ungerader natürlicher Zahlen ≥ 3 , die alle ungeraden Primzahlen enthält. Teile n der Reihe nach durch alle Zahlen u_{1}, u_{2}, u_{3}, …, die ≤ ⌊\sqrt{n}⌋ sind . Man findet dann entweder einen echten Teiler von n oder stellt fest, daß n eine Primzahl ist.

\underline{(6.10) BEM:} a) Beispiele für die Folge (u_{k})_{k∈ℕ} findet man in (5.25) .

b) Diese Methode ist günstig, wenn n kleine Teiler besitzt, wird aber sehr aufwendig,wenn n Teiler bei ⌊\sqrt{n}⌋ besitzt, oder sogar prim ist. Um Teiler in der Nähe von ⌊\sqrt{n}⌋ zu finden, kann man u.U. das Verfahren von Fermat anwenden, das auf dem folgenden Satz basiert:

\underline{(6.11) SATZ:} Sei n ∈ ℕ eine ungerade Zahl. Ferner seien

T := { (a, b) | a, b ∈ ℕ , n = a · b , a ≥ b > 0 } , D := { (x, y) | x, y ∈ ℕ_{0} , n = x^{2} − y^{2} } .

Dann ist die Abbildung f : T ⟶ D , (a, b) ⟼ (\frac{a + b}{2} , \frac{a − b}{2}) bijektiv.

(6.12) Das Verfahren von Fermat: Sei n ≥ 3 eine ungerade natürliche Zahl. Setze x := ⌊\sqrt{n}⌋ Teste, ob x^{2} − n Quadrat einer natürlichen Zahl y Wenn ja, gilt n = x^{2} − y^{2} = (x + y) · (x − y) , und es ist ein Teiler von n gefunden. Wenn nein, setze das Verfahren mit x := ⌊\sqrt{n}⌋ + 1 fort, usw. Brich das Verfahren ab, wenn x^{2} − n eine Qudratzahl ist.

\underline{Beispiel:} Finde einen Teiler von n = 200 819 :

x  x^{2} − n Quadratzahl Grund
⌊\sqrt{n}⌋ = 448  −115  nein  −115 ∉ ℕ_{0}
⌊\sqrt{n}⌋ + 1 = 449  782  nein  27^{2} = 729 und 28^{2} = 784
⌊\sqrt{n}⌋ + 2 = 450 1 681  ja  1 681 = 41^{2}

Mit y := 41 gilt also x^{2} − n = y^{2} , und damit n = x^{2} − y^{2} = (x + y) · (x − y) = (450 + 41) · (450 − 41) = 491 · 409 Da 409 und 491 Primzahlen sind, hat man sogar schon die PFZ von n gefunden, insbesondere ist n keine Primzahl.

Die Euler’sche φ–Funktion

\underline{(6.13) DEF:} Für n ∈ ℕ bezeichne φ(n) die Anzahl der Zahlen aus \{1, 2, 3, …, n\}, die zu n teilerfremd sind. Die Funktion φ : � ⟶ � , n ⟼ φ(n) , heißt Euler’sche Funktion .

\underline{(6.14) BEM:} a) Für n ∈ ℕ bezeichne R′_{n} die Menge

R′_{n} := { l | l ∈ ℕ, 1 ≤ l ≤ n, ggT(l, n) = 1 }

der Zahlen aus {1, 2, 3, …, n}, die zu n teilerfremd sind. Damit gilt φ(n) = |R′_{n}|.

b) φ(1) = 1 .

c) Für eine Primzahl p gilt φ(p) = p − 1 .

\underline{(6.15) SATZ:} Für p ∈ IP und k ∈ ℕ gilt φ(p^{k}) = p^{k} − p^{k−1} .

\underline{(6.16) SATZ:} Für \underline{teilerfremde} natürliche Zahlen m und n gilt:

a) R′_{mn} = { (lm + kn) mod (mn) | l ∈ R′_{n} , k ∈ R′_{m} }

b) φ(m · n) = φ(m) · φ(n) , d.h. φ ist multiplikativ .

\underline{(6.17) KOROLLAR:} Sind m_{1}, m_{2}, …, m_{r} (r ≥ 2) paarweise teilerfremde natürliche Zahlen, so gilt

φ(m_{1} · m_{2} · . . . · m_{r}) = φ(m_{1}) · φ(m_{2}) · . . . · φ(m_{r})

\underline{(6.18) SATZ:} Die natürliche Zahl n ≥ 2 besitze die kanonische Primfaktorzerlegung

n = ∏_{i=1}^{r} p_{i}^{k_{i}} .

Dann gilt  a) φ(n) = ∏_{i=1}^{r} (p_{i}^{k_{i}} − p_{i}^{k_{i}−1})  b) φ(n) = n · ∏_{i=1}^{r} (1 − \frac{1}{p_{i}} )

\underline{(6.19) BEM:} a) φ(n) = n · ∏_{p∈T_{IP}(n)} (1 − \frac{1}{p})

b) Die φ–Funktion besitzt entsprechende Eigenschaften wie die Teilerfunktion τ (vgl. (6.6)) .

c) Sei n = 43 560 . Berechne φ(n) : Bestimme die Primfaktorzerlegung: n = 2^{3} · 3^{2} · 5 · 11^{2} . Wende (6.18) an: φ(n) = (2^{3} − 2^{2})(3^{2} − 3)(5 − 1)(11^{2} − 11) = 4 · 6 · 4 · 110 = 10 560 . oder φ(n) = n · (1 − \frac{1}{2}) · (1 − \frac{1}{3}) · (1 − \frac{1}{5}) · (1 − \frac{1}{11}) = n · \frac{1}{2} · \frac{2}{3} · \frac{4}{5} · \frac{10}{11} = n · \frac{8}{33} = 10 560