§4 Quadrate in E(ℤ/nℤ)

Wir wollen die Quadratzahlen in E(ℤ/nℤ) studieren. Dabei betrachten wir insbesondere den Fall E(ℤ/pℤ) für eine Primzahl p. Wie bereits bekannt, ist

E := E(ℤ/pℤ) ≅ C_{p−1},

also

E = ⟨t̄⟩

für ein t̄ = t + pℤ ∈ E(ℤ/pℤ) ∖ {pℤ}. Die Zahl t ∈ ℤ heißt dann Primitivwurzel modulo p. Die Menge der Quadrate aus E sei im Folgenden mit E^{2} bezeichnet. Es ist

E^{2} = {x̄^{2} ∈ E | x̄ ∈ E} ≤ E.

Einen Ansatz liefert der Gruppen-Homomorphismus

σ := (x̄ ↦ x̄^{2}): E → E.

Der Kern zu diesem Gruppen-Homomorphismus ist gegeben durch

Kern(σ) = {x̄ ∈ E | x̄^{2} = ¯1 = 1 + pℤ} = ⟨−¯1⟩

Nach dem Homomorphiesatz für Gruppen gilt nun

E/⟨¯1⟩ > = E/Kern(σ) ≅ Bild(σ) = E^{2},

woraus

|E^{2}| = |E/⟨¯1⟩| = \frac{p − 1}{2}

folgt. Doch welche Elemente liegen nun in E^{2}? Gibt es zu einem gegebenen ā ∈ E ein b̄ ∈ E mit ā = b̄^{2}?

Ist zum Beispiel stets ā = −¯1 ∈ E^{2}? - Dem ist nicht so, es ist etwa

⟨¯1⟩ > ≤ E(ℤ/5ℤ)^{2},

aber

⟨¯1⟩ > ≰ E(ℤ/7ℤ)^{2}.

Definition 1 (Legendre-Symbol) Es seien a ∈ ℕ beliebig, p eine Primzahl und E^{2} := {x̄^{2} ∈ E(ℤ/pℤ) | x̄ ∈ E(ℤ/pℤ)}. Wir setzen

(\frac{a}{p}) := \{ \begin{matrix}+1, & falls ā ∈ E^{2}, \\ −1, & falls ā ∉ E^{2}. \end{matrix}

Für p = 7 ergibt sich zum Beispiel

(\frac{1}{7}) = (\frac{2}{7}) = (\frac{4}{7}) = 1 und (\frac{3}{7}) = (\frac{5}{7}) = (\frac{6}{7}) = −1.

Satz 1 (Eigenschaften von (\frac{a}{p})) Es seien a, b ∈ ℕ beliebig sowie p eine Primzahl.

(1) Aus a ≡ b mod p folgt (\frac{a}{p}) = (\frac{b}{p}).

(2) Für alle a ∈ ℤ ist (\frac{a^{2}}{p} ) = 1.

(3) Es ist (\frac{1}{p}) = 1.

(4) (\frac{a}{p}) · (\frac{b}{p}) = (\frac{ab}{p}).

Beweis. Es sei E := E(ℤ/pℤ) und E^{2} := {x̄^{2} ∈ E | x̄ ∈ E}.

(1) Aus a ≡ b mod p folgt ā = b̄ und damit (\frac{a}{p}) = (\frac{b}{p}).

(2) Für alle a ∈ ℤ ist \overline{a^{2}} = ā^{2} ∈ E^{2}, also (\frac{a^{2}}{p} ) = 1.

(3) Es ist ¯1 = ¯1^{2} ∈ E^{2}, somit folgt (\frac{1}{p}) = 1.

(4) Da |E^{2}| = \frac{p−1}{2} ist, folgt [E : E^{2}] = 2, also

E = E^{2} ˙∪ t̄E^{2}.

(Es gibt kein x̄ ∈ E mit t̄= x̄^{2}, denn o(t̄) = |E|.)

1. Fall: Es sei ā, b̄ ∈ E^{2}. Dann ist āb̄ = \overline{ab} ∈ E^{2}, also folgt

(\frac{a}{p}) · (\frac{b}{p}) = 1 · 1 = 1 = (\frac{ab}{p}) .

2. Fall: Es sei ā, b̄ ∉ E^{2}. Dann ist āb̄ = \overline{ab} ∈ E^{2}, also folgt

(\frac{a}{p}) · (\frac{b}{p}) = (−1) · (−1) = 1 = (\frac{ab}{p}) .

3. Fall: Es sei ā ∈ E^{2}, b̄ ∉ E^{2}. Dann ist āb̄ = \overline{ab} ∉ E^{2}, also folgt

(\frac{a}{p}) · (\frac{b}{p}) = 1 · (−1) = −1 = (\frac{ab}{p}) . ||

Bemerkung 1 Die Abbildung

(\frac{·}{p}) := (a ↦(\frac{a}{p})): ℤ ∖ \{0\} → \{±1\}

ist also ein Monoidhomomorphismus.

Satz 2 (Eulers Kriterium) Es sei p ≠ 2 eine Primzahl und a ∈ ℤ ∖ pℤ beliebig. Dann gilt

(\frac{a}{p}) ≡ a^{\frac{p−1}{2}} mod p.

Beweis. Es sei ā ∈ E := E(ℤ/pℤ) beliebig. Dann ist

ā^{p−1} = ¯1,

denn o(ā) | p − 1. Daraus folgt

(ā^{\frac{p−1}{2}} − ¯1) · (ā^{\frac{p−1}{2}} + ¯1) = ā^{p−1} − ¯1 = ¯0,

also, da ℤ/pℤ ein Körper ist,

ā^{\frac{p−1}{2}} ∈ \{±1\}.

1. Fall: Es sei (\frac{a}{p}) = 1. Dann gibt es also ein x̄ ∈ E mit ā = x̄^{2}. Somit folgt

\overline{a^{\frac{p−1}{2}}} = ā^{\frac{p−1}{2}} = (x̄^{2})^{\frac{p−1}{2}} = x̄^{p−1} = ¯1

und damit

a^{\frac{p−1}{2}} ≡ 1 mod p.

2. Fall: Es sei (\frac{a}{p}) = −1. Weiter sei t̄∈ E mit E = <t̄>. Dann ist

ā = t̄^{k} für ein ungerades k ∈ {0, …, p − 1}.

Außerdem ist t̄^{\frac{p−1}{2}} = −¯1 das Element der Ordnung 2 in E. Daraus folgt

\overline{a^{\frac{p−1}{2}}} = ā^{\frac{p−1}{2}} = (t̄^{j})^{\frac{p−1}{2}} = (t̄^{\frac{p−1}{2}} )^{j} = (−¯1)^{j} = −¯1,

also

a^{\frac{p−1}{2}} ≡ −1 mod p. ||

Beispiel 1 Es sei a = −1 und p eine Primzahl. Dann ist

(\frac{−1}{p}) ≡ (−1)^{\frac{p−1}{2}} = \{ \begin{matrix}+1, & für p ≡ 1 mod 4, \\ −1, & für p ≡ 3 mod 4, \end{matrix} mod p.

Satz 3 (quadratisches Reziprozitätsgesetz von Legendre und Gauss) Es seien p, q ≠ 2 Primzahlen mit p ≠ q. Dann ist

(\frac{p}{q}) (\frac{q}{p}) = (−1)^{\frac{p−1}{2} · \frac{q−1}{2}} .

Beweis. Siehe Literatur über Elementare Zahlentheorie. ||

Beispiel 2 Es ist

(\frac{23}{59}) = (\frac{59}{23}) · (−1)^{29·11}
= (−1) · (\frac{13}{23})
= (−1) · (\frac{23}{13}) · (−1)^{11·6}
= (−1) · (\frac{10}{13})
= (−1) · (\frac{−3}{13})
= (−1) · (\frac{−1}{13}) (\frac{3}{13})
= (−1) · (\frac{13}{3}) · (−1)^{6·1}
= (−1) · (\frac{1}{3})
= −1.

Satz 4 (zweite Komplementärformel) Es sei p ≠ 2 eine Primzahl. Dann ist

(\frac{2}{p}) = (−1)^{\frac{p^{2}−1}{8}} .

Beweis. Siehe Literatur über Elementare Zahlentheorie. ||

§6 Der Hauptsatz der Arithmetik

Frage 1 Warum gilt der Satz über die Existenz und Eindeutigkeit der Darstellung von natürlichen Zahlen als Produkt von Primzahlen?

Frage 2 Was ist eine Primzahl?

Satz 5 \sqrt{2} ist eine irrationale Zahl. Beweis. (nach Euklid, ca. 340 - 270 v. Chr.) Angenommen, \sqrt{2} ist eine rationale Zahl. Dann gibt es m, n ∈ ℕ mit ggT(m, n) = 1, so dass

\sqrt{2} = \frac{m}{n}.

Es folgt

2 = \frac{m^{2}}{n^{2}}

also

m^{2} = 2n^{2}.

Dann gilt aber 2 | m, es gibt also ein x ∈ ℕ mit m = 2x. Somit erhalten wir

4x^{2} = 2n^{2}

also

2x^{2} = n^{2},

also 2 | n im Widerspruch dazu, dass ggT(m, n) = 1 ist. ||

Zur Erinnerung:

Definition 2 (größter gemeinsamer Teiler) Es seien M ein Monoid und a, b ∈ M. Ein größter gemeinsamer Teiler von a, b ist ein g ∈ M für das gilt:

(1) g | a und g | b.

(2) Ist u ∈ M mit u | a und u | b, so folgt u | g.

Der Beweis zum vorigen Satz benutzte die Existenz und Eindeutigkeit der Primfaktorzerlegung einer natürlichen Zahl. Gilt in ℕ stets ”aus 2 | xy folgt 2 | x oder 2 | y“?

Definition 3 (unzerlegbare Elemente) Es sei M ein Monoid. Ein Element u ∈ M heißt unzerlegbar, wenn

(1) u kein Nullelement ist (n ∈ M heißt Nullelement, wenn nx = n für alle x ∈ M),

(2) u ∉ E(M) ist und

(3) aus u = ab folgt, dass a ∈ E(M) oder b ∈ E(M) ist.

Definition 4 (prime Elemente) Es sei M ein Monoid. Ein Element p ∈ M heißt prim, wenn

(1) p kein Nullelement ist,

(2) p ∉ E(M) ist und

(3) aus p = ab folgt, dass p | a oder p | b.

Frage 3 Ist unzerlegbar gleich prim in allgemeinen Monoiden?

Beispiel 3 (1) In ℕ ist unzerlegbar gleich prim. Ebenso in M_{1} := 2ℕ_{0} + 1 und M_{2} := 3ℕ_{0} + 1.

(2) Betrachten wir jedoch als Gegenbeispiel

M := 2ℕ_{0} ∪ {1}.

In diesem Monoid ist 42 unzerlegbar (denn 21 ∉ M), aber nicht prim, denn

420 = 6 · 70

und

42 ∤ 6 und 42 ∤ 70.

Frage 4 Woran liegt es, dass in ℕ unzerlegbare Element auch prim sind (und umgekehrt), in allgemeinen Monoiden jedoch nicht?