Chr.Nelius : Zahlentheorie (SS 2007) 1

§ 13. Quadratische Reste

Wir behandeln jetzt bei den Potenzresten den Spezialfall \underline{m = 2} und führen die folgende Begriffsbildung ein: \underline{(13.1) DEF:} Seien n ∈ ℕ und a ∈ ℤ teilerfremd. a heißt quadratischer Rest modulo n (abgekürzt QR mod n) , wenn die Kongruenz

x^{2} ≡ a (mod n)

lösbar ist, d.h. wenn a 2–ter Potenzrest modulo n ist. Anderenfalls heißt a quadratischer Nichtrest modulo n (abgekürzt QNR mod n) . Wir spezialisieren zunächst einige frühere Ergebnisse auf den Fall m = 2 . Aus (12.12) folgt: \underline{(13.2) BEM:} Besitzt die natürliche Zahl n ≥ 2 die kanonische Primfaktorzerlegung n = p_{1}^{k_{1}} · p_{2}^{k_{2}} · . . . · p_{r}^{k_{r}} , so ist eine zu n teilerfremde Zahl a ∈ ℤ genau dann QR mod n, wenn a QR mod p_{i}^{k_{i}} für alle i = 1, 2, …, r ist. \underline{(13.3) BEM:} Aus (12.16) folgt: Seien a ∈ ℤ ungerade und k ∈ ℕ mit k ≥ 3 . Genau dann ist a QR mod 2^{k}, wenn gilt:

i) a ≡ 1 (mod 4) und ii) a^{2^{k−3}} ≡ 1 (mod 2^{k}) . \underline{(13.4) LEMMA:} Seien k ∈ ℕ , k ≥ 3 und a ∈ ℤ. Dann gilt:

a) a QR mod 2 ⟺ a ≡ 1 (mod 2)

b) a QR mod 4 ⟺ a ≡ 1 (mod 4)

c) a QR mod 2^{k} ⟺ a ≡ 1 (mod 8) . Da es Primitivwurzeln mod p^{k} gibt (p ∈ IP , p > 2) , folgt aus (12.14) \underline{(13.5) BEM:} Seien p ∈ IP , p > 2 und k ∈ ℕ. Eine Zahl a ∈ ℤ mit p |̸ a ist genau dann ein QR modulo p^{k}, wenn gilt:

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

\underline{(13.6) SATZ:} Seien p ∈ IP , p > 2 und a ∈ ℤ mit p |̸ a. Dann folgt:

a) a ist genau dann QR mod p, wenn a^{\frac{p−1}{2}} ≡ 1 (mod p) gilt.

b) a ist genau dann QNR mod p, wenn a^{\frac{p−1}{2}} ≡ −1 (mod p) gilt. \underline{(13.7) KOROLLAR:} p sei eine ungerade Primzahl, und es seien a ∈ ℤ und k ∈ ℕ. Dann sind folgende Aussagen äquivalent:

a) a ist QR mod p^{k} b) a ist QR mod p.

\underline{(13.8) KOROLLAR:} Sei p eine ungerade Primzahl. Dann gilt:

a) Das Produkt zweier QR’e mod p ist ein QR mod p.

b) Das Produkt zweier QNR’e mod p ist ein QR mod p.

c) Das Produkt eines QR’es mod p und eines QNR’es mod p ist ein QNR mod p.

\underline{(13.9) DEF:} Sei p > 2 eine (ungerade) Primzahl. Ist dann die Zahl a ∈ ℤ teilerfremd zu p, so ist das Legendre–Symbol (\frac{a}{p}) (lies: “a nach p”) definiert durch:

(\frac{a}{p}) := \{ \begin{matrix}1 , & wenn a QR mod p ist \\ −1 , & wenn a QNR mod p ist . \end{matrix}

Adrien Marie Legendre (1752–1833), französischer Mathematiker.

(13.10) Kriterium von Euler Seien p ∈ IP , p > 2 und a ∈ ℤ mit p |̸ a. Dann gilt

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

Leonhard Euler (1707–1783), Schweizer Mathematiker.

\underline{(13.11) KOROLLAR:} a) Für eine Primzahl p > 2 gilt (\frac{−1}{p}) = (−1)^{\frac{1}{2} (p − 1)} .

b) −1 ist genau dann QR mod p, wenn p ≡ 1 (mod 4) gilt.

c) −1 ist genau dann QNR mod p, wenn p ≡ 3 (mod 4) gilt.

(13.12) Rechenregeln für das Legendre–Symbol Sei p > 2 eine ungerade Primzahl. Die Zahlen a, b, c ∈ ℤ seien alle teilerfremd zu p. Dann gilt:

a) a ≡ b (mod p) ⟹ (\frac{a}{p}) = (\frac{b}{p})

b) (\frac{a · b}{p}) = (\frac{a}{p}) · (\frac{b}{p}) c) (\frac{ac^{2}}{p} ) = (\frac{a}{p}).

\underline{(13.13) BEM:} Sei p eine ungerade Primzahl.

a) Dann ist {0, 1, 2, …, p − 1} ein vRS mod p. Wir werden im folgenden auch das folgende vRS mod p betrachten

\{−\frac{p − 1}{2}, −\frac{p − 3}{2}, …, −2, −1, 0, 1, 2, … \frac{p − 3}{2}, \frac{p − 1}{2}\} ,

das wir das System der absolut kleinsten Reste modulo p nennen.

b) Zu jeder Zahl a ∈ ℤ mit p |̸ a existiert genau eine Zahl r ∈ ℤ mit i) a ≡ r (mod p) und ii) 0 < | r | = min\{ | b | | b ∈ [a]_{p} \} ≤ \frac{1}{2} (p − 1) < \frac{1}{2} p.

\underline{(13.14) LEMMA:} Sei p eine ungerade Primzahl, und es sei S := \{1, 2, 3, …, \frac{1}{2} (p − 1)\}. Ferner sei a ∈ ℤ mit p |̸ a. Dann gilt:

a) Zu jedem s ∈ S existieren eindeutig bestimmte Zahlen ε_{s}(a) ∈ {+1, −1} und s_{a} ∈ S mit der Eigenschaft s · a ≡ ε_{s}(a) · s_{a} (mod p) .

b) Die Abbildung β_{a} : S ⟶ S , s ⟼ s_{a} ist bijektiv.

(13.15) Lemma von Gauß

Seien p > 2 eine Primzahl und a ∈ ℤ mit p |̸ a. Dann gilt

(\frac{a}{p}) = ∏_{s∈S} ε_{s}(a) = (−1)^{α} ,

wobei α die Anzahl der Zahlen unter \{a, 2a, 3a, …, \frac{1}{2} (p − 1) · a \} ist, die modulo p einen negativen absolut kleinsten Rest haben .

Carl Friedrich Gauß (1777–1855), deutscher Mathematiker

\underline{(13.16) KOROLLAR:} Sei p > 2 . Dann gilt:

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

b) 2 ist genau dann QR mod p, wenn p ≡ 1 (mod 8) oder p ≡ 7 (mod 8) gilt.

c) 2 ist genau dann QNR mod p, wenn p ≡ 3 (mod 8) oder p ≡ 5 (mod 8) gilt.

(13.17) Quadratisches Reziprozitätsgesetz für das Legendre–Symbol

Für verschiedene ungerade Primzahlen p und q gilt

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

Dieses Ergebnis wurde 1785 von Legendre vermutet, aber noch nicht vollständig bewiesen. Ein erster Beweis dafür wurde von Gauß erbracht (1801), der insgesamt 8 verschiedene Beweise gefunden hat. Insgesamt gibt es mehr als 100 Beweise für diesen Satz.

\underline{(13.18) BEM:} Stellt man a ∈ ℤ \ \{0\} in der Form

a = (−1)^{k}2^{l}p_{1}^{k_{1}} · . . . · p_{r}^{k_{r}}

dar mit k ∈ {0, 1}, l ≥ 0, r ≥ 0, k_{i} ≥ 1 , wobei p_{1}, …, p_{r} paarweise verschiedene ungerade Primzahlen sind, so gilt für eine ungerade Primzahl p mit p |̸ a

(\frac{a}{p}) = (\frac{−1}{p})^{k} · (\frac{2}{p})^{l} · (\frac{p_{1}}{p} )^{k_{1}} · . . . · (\frac{p_{r}}{p} )^{k_{r}} .

Die Legendre–Symbole (\frac{p_{i}}{p} ) lassen sich häufig mit (13.17) vereinfachen und berechnen.

Chr.Nelius : Zahlentheorie (SS 2007) 4 Das \underline{Jacobi–Symbol} ist eine Verallgemeinerung des Legendre–Symbols. Carl Gustav Jacob Jacobi (1804–1851), deutscher Mathematiker \underline{(13.19) DEF:} Seien a, b ∈ ℤ teilerfremde Zahlen, wobei b ≥ 3 ungerade ist. Besitzt dann b die Primfaktorzerlegung b = p_{1}^{k_{1}} · p_{2}^{k_{2}} · . . . · p_{r}^{k_{r}} mit paarweise verschiedenen (ungeraden) Primzahlen p_{1}, p_{2}, …, p_{r} und Exponenten k_{i} ≥ 0 , so ist das Jacobi–Symbol (\frac{a}{b}) definiert durch

(\frac{a}{b}) := ∏_{i=1}^{r} (\frac{a}{p_{i}} )^{k_{i}} .

Hierbei ist (\frac{a}{p_{i}} ) das “normale” Legendre–Symbol.

\underline{Beispiel:} (\frac{6}{245}) = (\frac{6}{5}) · (\frac{6}{7})^{2} = (\frac{6}{5}) = (\frac{1}{5}) = 1

\underline{(19.20) BEM:} a) Da b ungerade ist, sind auch alle Primfaktoren p_{i} von b ungerade und teilen a nicht wegen ggT(a, b) = 1 . Folglich ist (\frac{a}{p_{i}} ) definiert. Ist b = p eine ungerade Primzahl, so erhalten wir die alte Definition des Legendre–Symbols.

b) Es gilt (\frac{a}{b}) ∈ \{+1, −1\}

c) (\frac{a}{b}) = −1 ⟹ a ist QNR modulo b

d) Aus (\frac{a}{b}) = 1 läßt sich aber i.a. nicht schließen, daß a QR modulo b ist. Gegenbeispiel: (\frac{2}{15}) = 1 , aber 2 ist QNR modulo 15 , da 2 QNR modulo 3 ist. (13.21) Rechenregeln für das Jacobi–Symbol Seien a, a′, b, b′, c ∈ ℤ, wobei b ≥ 3 und b′ ≥ 3 beide ungerade sind. Dann gilt:

a) Aus a ≡ a′ (mod b) und ggT(a, b) = ggT(a, b′) = 1 folgt (\frac{a}{b}) = (\frac{a′}{b} )

b) Aus ggT(aa′, b) = 1 folgt (\frac{a · a′}{b} ) = (\frac{a}{b}) · (\frac{a′}{b} )

c) Aus ggT(a, bb′) = 1 folgt (\frac{a}{b · b′} ) = (\frac{a}{b}) · (\frac{a}{b′} )

d) Aus ggT(ac, b) = 1 folgt (\frac{a · c^{2}}{b} ) = (\frac{a}{b})

e) Aus ggT(a, bc) = 1 folgt (\frac{a}{b · c^{2}} ) = (\frac{a}{b})

Chr.Nelius : Zahlentheorie (SS 2007) 5 \underline{(13.22) HILFSSATZ:} Für ungerade Zahlen u, v ∈ ℤ gilt:

a) \frac{u − 1}{2} + \frac{v − 1}{2} ≡ \frac{uv − 1}{2} (mod 2)

b) \frac{u^{2} − 1}{8} + \frac{v^{2} − 1}{8} ≡ \frac{(uv)^{2} − 1}{8} (mod 8)

\underline{(13.23) LEMMA:} Für jede ungerade ganze Zahl b ≥ 3 gilt (\frac{−1}{b}) = (−1)^{\frac{b−1}{2}} .

\underline{(13.24) LEMMA:} Für jede ungerade ganze Zahl b ≥ 3 gilt (\frac{2}{b}) = (−1)^{\frac{b^{2}−1}{8}} .

(13.25) Quadratisches Reziprozitätsgesetz für das Jacobi–Symbol Für ungerade teilerfremde Zahlen a und b, die beide ≥ 3 sind, gilt:

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