Home > Documents > Elementare Zahlentheorie - TU Kaiserslauternfieker/pub/ezt01c.pdf2. LINEARE DIOPHANTISCHE...

Elementare Zahlentheorie - TU Kaiserslauternfieker/pub/ezt01c.pdf2. LINEARE DIOPHANTISCHE...

Date post: 30-Jul-2020
Category:
Author: others
View: 0 times
Download: 0 times
Share this document with a friend
Embed Size (px)
of 48 /48
Elementare Zahlentheorie Vorlesung im Sommersemester 2012 TU-Kaiserslautern gehalten von C. Fieker Version vom 9. Juli 2012
Transcript
  • Elementare Zahlentheorie

    Vorlesung imSommersemester 2012

    TU-Kaiserslautern

    gehalten vonC. Fieker

    Version vom 9. Juli 2012

  • Inhaltsverzeichnis

    Kapitel 1. Einführung 1

    Kapitel 2. Lineare Diophantische Gleichungen 3

    Kapitel 3. Multiplikative Funktionen 9

    Kapitel 4. Kryptographie: RSA 17

    Kapitel 5. Primitivwurzeln modulo N 191. Quadratische Reste 241.1. Rabin-Cryptosystem 311.2. Das Quadratische Sieb 32

    Kapitel 6. Quadratische Zahlkörper 35

    Anhang A. Übungszettel 45

    i

  • KAPITEL 1

    Einführung

    Elementare Zahlentheorie ist nicht elementar. Das Wort elementar bedeutet, dasssie sich im wesentlichen mit dem Ring Z der ganzen Zahlen beschäftigt und nichtmit komplizierteren Ringen wie Z[i] z.B..

    Andererseits werden viel, sehr viel komplizierte Techniken benutzt um Aussagenüber Z zu zeigen.

    Fragen, die untersucht werden:

    • Wie viele Primzahlen gibt es?• Gibt es ∞ viele Primzwillinge, also Primzahlen p wo p+ 2 auch Prim ist. Was

    ist mit Primdrillingen?• Wie kann ich feststellen ob eine Zahl Prim ist?• Wie viele ganze Lösungen hat der Satz von Pythargoras? (a2 + b2 = c2)• Gibt es x, y ∈ Z mit x2 ± dy2 = ±1?• Gibt es (viele) Primzahlen mit p ≡ i mod N?• Gibt es Zahlen mit der Eigenschaft, dass sie die Summe aller Teiler sind?• Wie viele Zahlen < 10000 gibt es die quadratfrei sind, nur Primteiler < 20

    haben, ...

    Viele dieser Frage sind einfach zu stellen aber sehr schwer zu beantworten. Oft wollenwir die Frage auch explizit beantworten, z.B. wollen wir ein/alle x, y mit x2+dy2 = 1haben. Wie wir sehen werden so gibt es maximal endlich viele Lösungen für d > 0und, wenn es überhaupt welche gibt, unendlich viele für d < 0. Wie wir auch sehenwerden sind die Lösungen aber sehr groß, die kleinste Lösung kann etwa log |x| =√d sein, also kann man das nicht sinnvoll durch ausprobieren lösen. (Andererseits:

    Prinzipiell kann man natürlich einfach alle Paare (x, y) ∈ Z2 ausprobieren. Wenn eseine Lösung gibt, so werden wir sie finden.)

    Gleichungen bei denen nur ganze Lösungen gesucht werden heißen Diophantisch.

    Man kann zeigen (nicht elementar), dass es schon keinen Algorithmus geben kann,der nur für alle f ∈ Z[x, y] entscheiden kann ob es Lösungen gibt. Daher werden hiersehr viele Klassen von Problemen explizit direkt untersucht während theoretischeMethoden untersucht werden die

    ”häufig“ klappen.

    1

  • KAPITEL 2

    Lineare Diophantische Gleichungen

    Beispiel 2.1: Seien A ∈ Zn×m und b ∈ Zn beliebig. Gibt es x ∈ Zm mit Ax = b?

    Mit dem Gauß-Algorithmus kann man einfach testen, ob es solche x ∈ Qm gibt, aberZ? Hier werden wir nur den Fall n = 1 vollständig untersuchen.Definition 2.2: Es sei R ein (kommutativer) Ring (mit Eins).

    (1) a ∈ R heißt Nullteiler, falls es b 6= 0 gibt mit ab = 0(2) Falls R keine Nullteiler 6= 0 hat, so heißt R Integritätsring.(3) Wir schreiben a|b (

    ”a teilt b“) falls es ein c ∈ R gibt mit ac = b

    (4) p ∈ R heißt Primelement, falls aus p|ab immer p|a oder p|b folgt.(5) R∗ := {x ∈ R|∃y ∈ R : xy = 1}(6) p ∈ R heißt irreduzibel, falls aus p = ab immer a ∈ R∗ oder b ∈ R∗ folgt.

    Jedes Primelement ist irreduzibel.(7) a, b ∈ R heissen assoziiert falls es c ∈ R∗ gibt mit a = bc. Dies ist äquivalent

    zu a|b und b|a.(8) R heißt Hauptidealring falls es für jedes Ideal A < R ein a ∈ R gibt mit

    A = (a) = aR.

    Satz 2.3: Es sei R ein Hauptidealring. Dann gilt

    (1) Jedes irreduzible Element ist prim.(2) Jedes a ∈ R \ {0} hat eine bis auf die Reihenfolge und bis auf Einheiten

    eindeutige Zerlegung in Primfaktoren. Also ist R ein ZPE oder faktoriellerRing.

    Bemerkung 2.4: In dieser Vorlesung sind Primzahlen immer positive Primele-mente in Z. Also ist 2 eine Primzahl, −2 jedoch nicht. Andererseits ist −2 einPrimelement in Z. 1 ist keine Primzahl und auch kein Primelement.

    Mit dieser Vereinbarung hat jede positive ganze Zahl eine eindeutige Zerlegung inPrimzahlen wenn wir diese nach der Größe sortieren. Die Menge der Primzahlen istP oder PZ.

    Satz 2.5 (Division mit Rest): Seien a und b ∈ Z, b 6= 0. Dann gibt es q und r ∈ Zmit a = qb+ r und 0 ≤ r < |b|. (Also ist Z ein Euklidischer Ring).Satz 2.6 (ggT): Für a, b ∈ Z, nicht beide 0, gibt es 0 < g ∈ Z mit g = max{x :x|a, x|b}, g heißt der grösste gemeinsame Teiler (ggT) von a und b.a, b heissen teilerfremd falls ggT(a, b) = 1 gilt.Für a, b ∈ Z, nicht 0, gibt es 0 < k ∈ Z mit g = min{x : a|x, b|x}, k ist daskleinste gemeinsame Vielfache (kgV ) von a und b.

    Definition 2.7: Es sei 0 6= a ∈ Z und p eine Primzahl. Wir schreiben pl‖a fallspl|a und pl+1 6 |a, in diesem Fall np(a) := l. Für p 6 |a gilt np(a) = 0.Ferner np(0) := ∞ und für a/b ∈ Q setzen wir np(a/b) := np(a)− np(b).

    3

  • 4 2. LINEARE DIOPHANTISCHE GLEICHUNGEN

    Bemerkung 2.8: Damit gilt für alle 0 6= a ∈ Q:|a| = ∏

    p∈Ppnp(a)

    Ferner gilt:

    (1) a|b ⇔ (a) ⊇ (b) ⇔ np(a) ≤ np(b) für alle p ∈ P(2) a|b und b|a ⇔ (a) = (b)(3) g = ± ggT(a, b) ⇔ (g) = (a, b)(4) np(ggT(a, b)) = min(np(a), np(b))(5) np(kgV (a, b)) = max(np(a), np(b))(6) |ab| = ggT(a, b) kgV (a, b)(7) ggT(a, b) = ggT(a, b+ ac) für alle c ∈ Z(8) np(ab) = np(a) + np(b) für a, b ∈ Q(9) np(a+ b) ≥ min(np(a), np(b)) für a, b ∈ Q.

    (10) Sei a ∈ Q. Dann gilt a ∈ Z ⇔ np(a) ≥ 0 für alle p ∈ P.Dies wurde (fast) alles schon in der AGS bewiesen. Es ist hier nur zur Wiederholungaufgezählt.

    Definition 2.9: Sei a, b ∈ Z, 0 < n ∈ Z. Wir schreiben a ≡ b (mod n) genaudann, wenn n|(a− b) gilt. (a kongruent b modulo n).Für jedes n > 0 definiert dies eine Äquivalenzrelation auf Z, a ∼ b ⇔ a ≡ b(mod n) ⇔ n|(a− b).Die Äquivalenzklassen ā = {a+kn|k ∈ Z} bilden einen Ring mittels ā+ b̄ := a+ bund āb̄ = ab. In AGS wurde gezeigt, dass dies wohldefinierte Operationen sind.Zusätzlich haben wir die Projektion:

    π : Z→ Z/mZ : a 7→ āeinen surjektiven Ringhomomorphismus mit Kern ker π = nZ.Es gilt (Z/nZ)∗ = {ā| ggT(a, n) = 1}. Z/nZ ist ein Körper genau dann, wennn ∈ P gilt.Bemerkung 2.10: Etwas allgemeiner als oben gilt:

    φ : Z/nZ→ Z/mZ : ā = a+ nZ→ a+mZist ein wohldefinierter surjektiver Ringhomomorphismus genau dann, wenn m|n gilt.Satz 2.11 (Chinesischer Restsatz): Seien ni ∈ Z paarweise Teilerfremd. Dann gilt

    Z/(∏ni)Z ∼ ×Z/niZ

    (wobei ∼: ā = a (mod ∏)ni 7→ (a (mod n)i)i ein Ringisomorphismus ist.)Insbesondere gilt dann für n :=

    ∏ni das die Einheitengruppen ebenfalls isomorph

    sind:(Z/nZ)∗ ∼ ×(Z/niZ)∗

    Damit gibt es für alle bi ∈ Z ein x ∈ Z mit x ≡ bi (mod n)i für alle i. Dieses x istmodulo n eindeutig: sei x̃ eine weitere Lösung, dann gilt x ≡ x̃ (mod n).Beispiel 2.12: Wir suchen x mit x ≡ 1 (mod 6), x ≡ 2 (mod 5) und x ≡ 3(mod 7). Zunächst berechnen wir Produkte und Inverse: 5 · 6 = 30 ≡ 2 (mod 7),6 · 7 = 42 ≡ 2 (mod 5), 3 · 7 = 35 ≡ 5 (mod 6), 2 · 4 ≡ 1 (mod 7), 2 · 3 ≡ 1 (mod 5)und 5·5 ≡ 1 (mod 6). Damit erhalten wir dann 1·35·5+2·42·3+3·30·4 = 787 ≡ 157(mod 6 · 7 · 5)

  • 2. LINEARE DIOPHANTISCHE GLEICHUNGEN 5

    Bemerkung 2.13: Der Chinesische Restsatz zeigt auch, dass Z/nZ × Z/mZ alsGruppe zyklisch ist - falls ggT(n,m) = 1 gilt. Wir werden später versuchen dieEinheitengruppe besser zu verstehen.

    Definition 2.14: Seien xi ∈ Z beliebig, nicht alle gleichzeitig 0. 0 < g ∈ Z heißtgrößter gemeinsamer Teiler (ggT) von x1, . . ., xr genau dann, wenn

    g = max{0 < y|y|x1, . . . , y|xr}gilt.Die xi heissen teilerfremd, falls ggT(x1, . . . , xr) = 1 gilt.

    Bemerkung 2.15: In diesem Fall gibt es y1, . . ., yr mit g =∑r

    i=1 xiyi. Die yi (undg) können z.B. mit dem Euklidischen Algorithmus induktiv gefunden werden: Seix = (12, 15, 20). Dann gilt ggT(12, 15) = 3 = −1 · 12 + 1 · 15 und ggT(3, 20) = 1 =7·3−1·20, also 1 = ggT(12, 15, 20) = 7·(−1·12+1·15)−1·20 = −7·12+7·15−1·20.Achtung: die Darstellung hängt von der Reihenfolge ab! Das Problem eine

    ”gute“

    Darstellung zu finden ist nicht einfach. Es gilt auch:

    1 = −12 · 12 + 11 · 15− 1 · 20 = 13 · 12 + 19 · 15− 22 · 20Achtung: teilerfremd und paarweise teilerfremd sind verschieden! In dem Beispielsind 12, 15, 20 teilerfremd (ggT = 1) aber nicht paarweise teilerfremd.

    Ähnlich wie in der AGS gilt auch hier

    (ggT(x1, . . . , xr)) = (x1, . . . , xr)

    Bemerkung 2.16: Aufgabe: es gilt (kgV (a, b)) = (a) ∩ (b) und (a) ∩ (b) = (ab)genau dann, wenn (a) + (b) = (1) gilt.

    Satz 2.17: Seien a1, . . ., ar ∈ Z, nicht alle Null und b ∈ Z beliebig. Dann ist dielineare Diophantische Gleichung

    r∑

    i=1

    aixi = b

    genau dann mit xi ∈ Z lösbar, falls ggT(a1, . . . , ar)|b gilt.

    Beweis. Sei x eine Lösung. Dann gilt∑r

    i=1 xiai = b und damit sofort b ∈ (a1, . . . , ar) =(ggT(a1, . . . , ar)).

    Andererseits, falls ggT(a1, . . . , ar)|b gilt, so können wir b = c ggT(a1, . . . , ar) schrei-ben und yi finden mit ggT(a1, . . . , ar) =

    ∑ri=1 yiai um eine Lösung zu finden. ¤

    Ähnlich wie im Falle von”normalen“ linearen Gleichungen kann man auch hier

    ”alle“ Lösungen parametrisieren. Es ist jedoch etwas komplizierter, da wir keine

    Vektorräume benutzen können. Daher werden wir hier eine (sehr spezielle) Klassevon

    ”Vektorräumen über Ringen“ untersuchen:

    Definition 2.18: Eine abelsche Gruppe M heißt Z-Modul falls es eine AbbildungZ×M →M : (z,m) 7→ zm gibt mit(1) Für alle a, b ∈M , r ∈ Z gilt r(a+ b) = ra+ rb(2) Für alle a ∈M , r, s ∈ Z gilt (r + s)a = ra+ sa(3) Für alle a ∈M , r, s ∈ Z gilt (r(sa)) = (rs)a(4) 1a = a für alle a ∈M .

  • 6 2. LINEARE DIOPHANTISCHE GLEICHUNGEN

    (Wie ein Vektorraum, aber über einem Ring)

    Beispiel 2.19: (1) Zn ist ein Z-Modul(2) Qn ist ein Z-Modul(3) Z[x](4) {x ∈ Zn|∑ aixi = 0}(5) Jede abelsche Gruppe ist ein Z-Modul

    Definition 2.20: Ein Z-Modul M heißt torsionsfrei falls für a ∈ M und r ∈ Zmit ra = 0 stets a = 0 oder r = 0 folgt.Eine Teilmenge S ⊆M eines Z-Moduls M heißt frei (linear unabhängig) falls aus∑xisi = 0 mit si ∈ S und xi ∈ Z immer xi = 0 folgt.

    Eine freie Teilmenge B ⊆M heißt Basis falls es für jedes y ∈M eine Darstellungy =

    ∑xibi mit xi ∈ Z und nur endlich viele xi 6= 0 gibt. Diese Darstellung ist

    dann natürlich eindeutig.

    Satz 2.21: Jeder endlich erzeugte torsionsfreihe Z-Modul M ⊆ Zn besitzt eineBasis. Die Mächtigkeit der Basis ist eindeutig.

    Bemerkung 2.22: Falls M nicht torsionsfrei ist, so gibt es 0 6= a ∈M und 0 6= r ∈Z mit ra = 0. In jeder

    ”Basisdarstellung“ a =

    ∑ribi gilt dann auch ra =

    ∑rribi = 0

    was natürlich nicht geht.

    Endlich erzeugt bedeutet, dass es eine endliche Teilmenge A ⊆M gibt so, dass jedesm ∈ M in der Form m = ∑ riai mit ai ∈ A und ri ∈ Z dargestellt werden kann.Diese Darstellung braucht nicht eindeutig zu sein!.

    Der Satz gilt in einem allgemeineren Rahmen.

    Beweis. Da Z ein Teilring von Q ist, können wir M ⊆ Zn ⊆ Qn betrachten. In Qnsetzen wir U := 〈M〉 den von M erzeugten Unterraum. Sei B̃ eine Basis von U undu ∈ U . Dann gibt es ri ∈ Q, mi ∈ M ⊆ Zn mit u = ∑ rimi, speziell folgt das esein du ∈ Z gibt mit duu ∈M (gemeinsamer Hauptnenner der ri). Also gibt es auchein d ∈ Z mit B := dB̃ ⊆ M . Da B̃ eine Basis (von U) ist, so gilt dies auch für B.Also ist B frei. (Frei heißt linear unabhängig, also aus

    ∑rbb = 0 mit rb ∈ Q muss

    rb = 0 folgen. Damit ist auch sofort klar, dass frei über Z (rb ∈ Z) und frei über Q(rb ∈ Q) das selbe sind.)Jetzt brauchen wir Induktion über die Dimension von U . Sei dimU = 1, also B = {b}und setze A := {q ∈ Q|qb ∈ M} ⊆ Q Wegen M ⊆ Zn gibt es d ∈ Z mit dA ⊆ Z(b = (b1, . . . , bn) ∈ Zn, q = r/t und qb ∈ M ⇐ qbi = rbi/t ∈ Z, also rbi ∈ tZ, damitt|rbi. Wenn wir ggT(r, t) = 1 annehmen, folgt dann t ≤ bi). Nun ist dA ≤ Z einIdeal, also dA = (a). Damit gilt dann M = a/db: Sei m ∈ M , dann gilt m = qbfür ein q ∈ Q. Sogar q ∈ A, damit dq ∈ (a), also q = ka/d mit k, a, d ∈ Z,m = qb = ka/db = k · a/db wie behauptet.Sei nun dimU = #B =: r > 1. mit B = {b1, . . . , br}. Definiere φ : U → Q :∑xibi 7→ x1 und setze A := φ(M). Wegen M endlich erzeugt gibt es d ∈ Z mit

    dA ⊆ Z. Da M ein Z-Modul ist und φ eine Q-lineare Abbildung ist dA ebenfalls einZ-Modul, also ein Ideal, daher gibt es a mit dA = (a). Setze nun c1 := a/db1, undN := kerφ ∩M = {m ∈ M |φ(m) = 0}. Offenbar gilt dim〈N〉Q ≤ r − 1 und N istein Z-Modul. Nach Induktionsvoraussetzung hat N eine Basis c2, . . ., cr. Dann istc1, . . ., cr eine Basis für M . Offenbar ist dies eine Basis für 〈M〉Q, also kann jedes

  • 2. LINEARE DIOPHANTISCHE GLEICHUNGEN 7

    m ∈M als m = ∑xici mit xi ∈ Q dargestellt werden. Nach Konstruktion gilt dannx1 ∈ Z (siehe φ!) und damit m− x1c1 ∈ N , also auch x2, . . ., xr ∈ Z.Die Aussage über die Mächtigkeit der Basis folgt sofort daraus, dass die jede Z-Basisfür M eine Q-Basis für 〈M〉Q ist. ¤Lemma 2.23: Sei M ⊆ Zn ein Z-Modul. Dann ist M endlich erzeugt.

    Beweis. Sei U := 〈M〉 der von U erzeugte Q-Vektorraum. Dann hat U eine BasisB̃ mit #B̃ ≤ n. Wie oben gibt es ein d > 0 mit B := dB̃ ⊆M . B kann zu einer Q-Basis C von Qn fortgesetzt werden, ähnlich wie oben können wir C ⊆ Zn und B ⊆ Cerreichen. Als Menge gilt nun M/〈B〉Z ⊂ Zn/〈C〉Z. Wenn nun Zn/〈C〉 endlich ist,so sind wir fertig. Zn hat eine Basis ei, also kann jedes x ∈ Zn in der Form ∑ xieimit xi ∈ Z dargestellt werden. Da C = {c1, . . . , cn} eine Q-Basis ist, gibt es ci,j ∈ Qmit ei =

    ∑nj=1 ci,jci. Via Hauptnenner gibt es nun e > 0 mit dei ∈ 〈C〉Z für alle i.

    Also ex ∈ 〈C〉Z für alle x ∈ Zn und damit #Zn/〈C〉Z ≤ en. ¤Bemerkung 2.24: Sei ai ∈ Z beliebig. Dann ist M := {x ∈ Zn|∑ xiai = 0} ein sol-cher Z-Modul, also gibt es eine Basis c1, . . ., cr und wir könnenM =

    ∑Zci schreiben.Falls nicht alle ai Null sind, folgt dann auch r = n− 1 aus den Vektorräumen.Allerdings können wir die Basis noch nicht bestimmen. Über Q geht dies mit demGauß-Algorithmus, aber hier können wir nicht teilen.

    Bemerkung 2.25: Sei T i,j = (T i,jk,l )k,l ∈ Zn×n die Matrix mit T i,jk,k = 1 für 1 ≤ k ≤ n,k 6= i, j, T i,ji,j = T i,jj,i = 1 und T i,jk,l = 0 sonst. Dann bewirkt die Multiplikation mitT i,j von rechts (links) das Vertauschen der i und jten Zeile (Spalte). Ferner giltdetT i,j = −1.Sei Si,j(a) = (Si,j(a)k,l)k,l ∈ Zn×n die Matrix mit Si,j(a)k,k = 1 für 1 ≤ k ≤ n,Si,j(a)i,j = a und S

    i,j(a)k,l = 0 sonst. Dann bewirkt die Multiplikation mit Si,j(a)

    von rechts (links), dass das a-fache der jten Zeile (Spalte) zur iten addiert wird. Esgilt detSi,j(a) = 1.

    Dies sind die elementaren Transformationen die wir nun benötigen.

    Satz 2.26 (Hermite Form): Sei A ∈ Zn×m beliebig. Dann gibt es eine MatrixU ∈ Zm×m mit detU = ±1 so, dass H := UA in Zeilen-Stufen-Form ist (ähnlichwie in GdM, aber hier sind keine 1en)Wir setzen Gl(m,Z) := {a ∈ Zm×m| det a = ±1}.

    Beweis. Per Induktion über die Spalten. Obda, sei die 1. Spalte von A nicht iden-tisch 0. Zunächst skalieren wir die Zeilen mit ±1 um die 1. Spalte ≥ 0 zu erhal-ten. Die Zeilenvertauschung die das oberste Element A1,1 minimiert ist in Gl(m,Z).Jetzt subtrahieren wir geeignete Vielfache der 1. Zeile von allen weiteren bis dieZeilenanfänge Ai,1, i > 1 alle A1,1 > Ai,1 ≥ 0 erfüllen. Die ist ebenfalls eine Ele-mentartransformation in Z. Jetzt tauschen wir wieder das kleinste Element der 1.Spalte nach oben und wiederholen den Vorgang bis in der 1. Spalte genau ein vonNull verschiedenes Element steht.

    Induktiv wird dies nun auf der Teilmatrix die durch das Entfernen der 1. Zeile undSpalte entsteht wiederholt.

  • 8 2. LINEARE DIOPHANTISCHE GLEICHUNGEN

    Damit erhalten wir eine Matrix H̃ als”obere Dreiecksmatrix“ und eine Transforma-

    tion Ũ ∈ Gl(m,Z).Indem wir nun noch geeignete Vielfache von den darüber liegenden Zeilen abziehen,können wir arangieren, dass die

    ”Diagonale“ die für die Spalte maximalen Einträge

    hat. ¤Bemerkung 2.27: Die Matrix H die als Ergebnis da steht ist eindeutig. Ein ana-loges Verfahren kann natürlich auch auf den Spalten durchgeführt werden.

    Beispiel 2.28: Wir wollen (alle) Lösungen von 6x + 10y + 15z = 7 bestimmen.Dazu wenden wir den Algorithmus auf die Matrix (6, 10, 15)t an:

    1 0 0 60 1 0 100 0 1 15

    1 0 0 6−1 1 0 4−2 0 1 3

    −2 0 1 3−1 1 0 41 0 0 6

    −2 0 1 31 1 −1 15 0 −2 0

    1 1 −1 1−2 0 1 35 0 −2 0

    1 1 −1 1−5 −3 4 05 0 −2 0

    So, von der 1. Zeile: 1 · 6 + 1 · 10 − 1 · 15 = 1 (also 7 · 6 + 7 · 10 − 7 · 15 = 7) und6x + 10y + 15z = 0 ⇔ (x, y, z) ∈ Z(−5,−3, 4) + Z(5, 0,−2). Damit haben wir alleLösungen parametrisiert!

    Bemerkung 2.29: Wie wir gesehen haben ist ein”einfach“ eine/alle Lösungen zu

    finden. Andererseits, kleine Lösugen zu finden ist ein hartes Problem an dem nochaktiv geforscht wird. Es gibt Verschlüsselungsverfahren die genau darauf beruhen,dass es schwer ist kleine Lösungen zu finden. Dies wird in der Gitterbasierten Kryp-tographie untersucht (Lattice Cryptography).

  • KAPITEL 3

    Multiplikative Funktionen

    Definition 3.1: Eine Funktion α : Z>0 → R heißt Zahlentheoretisch oder Arith-metisch. Eine zahlentheoretische Funktion α heißt multiplikativ genau dann, wennfür alle x, y ∈ Z>0 mit ggT(x, y) = 1 folgt α(xy) = α(x)α(y).Wir bezeichnen mit Z die Menge der multiplikativen Funktionen.Eine multiplikative Funktion α heißt vollständig multiplikativ falls α(xy) =α(x)α(y) für alle x, y ∈ Z>0 gilt.Beispiel 3.2: Die folgenden Funtionen sind multiplikativ, die letzten beiden sogarvollständig multiplikativ.

    (1) 0 : Z>0 → R : x 7→ 0(2) o : Z>0 → R : x 7→

    1 x = 1

    0 sonst

    (3) e : Z>0 → R : x 7→ 1(4) i : Z>0 → R : x 7→ xLemma 3.3: (1) Jedes α ∈ Z mit α 6= 0 erfüllt α(1) = 1.(2) Eine Funktion α : Z>0 → R ist genau dann multiplikativ wenn gilt

    α(∏

    p∈Ppnp) =

    p∈Pα(pnp)

    (3) Zwei multiplikative Funktionen sind genau dann gleich, wenn sie auf Prim-potenzen übereinstimmen.

    (4) Eine multiplikative Funktion α ist genau dann vollständig multiplikativ wennα(pn) = α(p)n gilt.

    Beweis. (1) 1 ist koprim zu jedem x ∈ Z, also ggT(x, 1) = x, damit1α(x) = α(x) = α(1x) = α(1)α(x)

    (2) Sei α 6= 0 (sonst ist es trivial). Wenn α multiplikativ ist, so folgt die Identitätsofort aus der Definition.Es gelte nun die Identität und es seien x, y ∈ Z>0 mit ggT(x, y) = 1 gegeben.Daher gilt dann x =

    ∏li=1 p

    nii und y =

    ∏ri=l+1 p

    nii und die pi sind paarwei-

    se verschieden, also xy =∏r

    i=1 pnii . Aus der Identität folgt dann sofort das

    α(x)α(y) = α(xy) ist.(3) Gilt α = β, so folgt sofort α(pn) = β(pn) für alle p ∈ P. Andererseits, falls

    α(pn) = β(pn) gilt, so folgt α = β aus (2).(4) Wenn α vollständig multiplikativ ist, so ist die Behauptung klar. Die Rückrich-

    tung folgt aus (2).

    ¤9

  • 10 3. MULTIPLIKATIVE FUNKTIONEN

    Definition 3.4: Für zwei arithmetische Funktionen α, β : Z>0 → R definierenwir die Dirichlet Faltung als

    α ? β(z) :=∑

    1≤d≤zd|z

    α(d)β(z

    d)

    Bemerkung 3.5: Wir können die Definition auch so schreiben:

    (α ? β)(n) =∑

    ab=n

    α(a)β(b)

    Wobei die Summe über alle Paare (a, b) ∈ Z2>0 mit ab = n läuft.

    Lemma 3.6: (1) Für zwei multiplikative Funktionen α, β ist auch α ? β multi-plikativ. Die Faltung vollständig multiplikativer Funktionen ist in der Regelnicht vollständig multiplikativ.

    (2) Faltung ist assoziativ: (α ? β) ? γ = α ? (β ? γ)(3) Faltung ist kommutativ, α ? β = β ? α(4) Für o gilt α ? o = α

    Beweis. (1) Seien n, m teilerfremd. Für jede Faktorisierung cz = nm können wirc = ab, a|n, b|m und z = xy, x|n, y|m schreiben. Hier gilt dann ggT(a, x) =ggT(b, y) = 1. Damit

    (α ? β)(nm) =∑

    cz=nm

    α(c)β(z)

    =∑

    ax=nby=m

    α(ax)β(by)

    =∑

    ax=nby=m

    α(a)α(x)β(b)β(y)

    =∑

    ab=n

    α(a)β(b)∑

    xy=m

    α(x)β(y)

    = (α ? β)(n)(α ? β)(m)

    (2)

    (α ? β) ? γ(n) =∑

    dc=n

    (α ? β)(d)γ(c)

    =∑

    dc=n

    (∑

    ab=d

    α(a)β(b))γ(c)

    =∑

    abc=n

    α(a)β(b)γ(c)

    (3) Die Kommutativität folgt sofort aus der vorherigen Bemerkung(4) (α ? o)(pn) =

    ∑i+j=n α(p

    i)o(pj) = α(pn), da o(pj) = 0 für j > 0 gilt.

    ¤

  • 3. MULTIPLIKATIVE FUNKTIONEN 11

    Satz 3.7: Für jede arithmetische Funktion mit α(1) 6= 0 gibt es eine arithmetischeFunktion β mit α ? β = o. Es gilt β(1)α(1) = 1 und für n > 1:

    β(n) =−1α(1)

    1≤d 1. Dann gelten

    0 = o(n) = (α ? β)(n) = α(1)β(n) +∑

    ab=nb0 → R : z 7→

    1 z = 1

    0 ∃p ∈ P : p2|z(−1)#{p:p|z} sonst

    Beispiel 3.10:z 1 2 3 4 5 6 7 8

    µ(z) 1 −1 −1 0 −1 1 −1 0

  • 12 3. MULTIPLIKATIVE FUNKTIONEN

    Lemma 3.11: Die Möbius Fuktion is multiplikativ (aber nicht vollständig). Fernergilt

    µ ? e = o

    also ist µ invers zu e.

    Beweis. Seien n, m Teilerfremd. Dann gilt {p ∈ P : p|mn} = {p ∈ P : p|n}∪̇{p ∈P : p|m} und damit die Multiplikativität.Da µ und e multiplikativ sind, so gilt dies auch für µ? e. Also reicht es die Identitätfür Primpotenzen nachzuweisen:

    (µ ? e)(pn) =∑

    ab=pnµ(a)e(b) = µ(1)e(pn) + µ(p)e(pn−1) = µ(1) + µ(p) = 0

    ¤Definition 3.12: Sei α Multiplikativ. Dann definieren wir die Summatorfunktion

    β : Z>0 → R : n 7→∑

    d|nα(d)

    wobei die Summe über alle (positiven) Teiler von n läuft.

    Satz 3.13: Ist α multiplikativ, so gilt dies auch für die Summatorfunktion β.Ferner gilt die Möbiussche Umkehrformel:

    α = β ? µ

    d.h. die Summatorfunktion β definiert α vollständig.

    Beweis. Offenbar gilt β = e ? α, also ist β multiplikativ. Aus dem Lemma folgtdann:

    α = α ? o = α ? (e ? µ) = β ? µ

    wie behauptet. ¤

    Definition 3.14 (Eulersche φ-Funktion): Die Eulersche φ-Funktion ist definiertals

    φ(n) := #{0 < m < n : ggT(m,n) = 1} = #(Z/nZ)∗und φ(1) := 1.

    Satz 3.15: (1) Die Eulersche φ-Funktion ist multiplikativ.(2) #(Z/pnZ)∗ = (p− 1)pn−1 = pn − pn−1(3) Sei n =

    ∏pnp . Dann gilt φ(n) =

    ∏φ(pnp) = n

    ∏p|n(1− 1p).

    Beweis. (1) Für n, m Teilerfremd folgt aus dem Chinesischen Restsatz sofort

    Z/(nm)Z ∼ Z/mZ× Z/nZals Ringe und daher

    (Z/(nm)Z)∗ ∼ (Z/mZ)∗ × (Z/nZ)∗für die Einheitengruppe.

    (2) Wir betrachten (Z/pnZ)∗ → (Z/pZ)∗ : x mod pn 7→ x mod p als Gruppenho-momorphismus. Er ist offensichtlich surjektiv mit Kern {1+px : 0 ≤ x < pn−1}(Gruppe der 1-Einheiten). Da alle Mengen hier endlich sind, folgt die Aussagedurch abzählen.

  • 3. MULTIPLIKATIVE FUNKTIONEN 13

    (3) Klar: pn − pn−1 = pn(1− 1p)

    ¤Beispiel 3.16: Aufgabe: (Um die Numerierung nicht zu ändern habe ich ein leeresBsp eingebaut)

    Beispiel 3.17:z 1 2 3 4 5 6 7 8

    φ(z) 1 1 2 2 4 2 6 4

    Lemma 3.18: Für die Summatorfunktion der φ-Funktion gilt:

    (φ ? e)(n) =∑

    d|nφ(d) = n

    (Damit kann φ(n) rekursiv berechnet werden)

    Beweis. Da alle Funktionen multiplikativ sind, reicht es die Behauptung für pn zuzeigen.

    (φ ? e)(pn) =n∑

    i=0

    φ(pi) = 1 +n∑

    i=1

    pi − pi−1 = pn

    ¤Bemerkung 3.19: Das Lemma werden wir später verwenden um die folgende Aus-sage zu zeigen: Ein endliche Gruppe G ist genau dann zyklisch, wenn es für jedenTeiler d der Gruppenordnung n = #G genau eine Untergruppe U gibt mit #U = d.

    Satz 3.20 (Euler): Sei n > 1 und 0 6= k ∈ Z beliebig mit ggT(n, k) = 1. Danngilt

    kφ(n) ≡ 1 mod nBeweis. ggT(n, k) = 1 impliziert k ∈ (Z/nZ)∗. Aus AGS und dem Satz von La-grange folgt damit ord k|φ(n) = #(Z/nZ)∗. ¤Bemerkung 3.21: Falls φ(n) berechnet werden kann (oder einfach nur bekanntist), kann dies auch zum Invertieren benutzt werden: kφ(n) ≡ 1 mod n ⇐⇒k · kφ(n)−1 ≡ 1 mod n Also ist kφ(n)−1 invers zu k. Falls φ(n) klein ist, so ist diesmanchmal Vorteilhaft. Auf dem Computer wird es jedoch nicht benutzt, da φ(n)schwer zu berechnen ist und es schneller geht einen ggT zu bestimmen, als die vie-len Multiplikationen durchzuführen.

    Korollar 3.22 (Fermat): Sei p ∈ P Prim. Dann gilt für alle k ∈ Z: kp ≡ k mod p

    Beweis. Für p|k ist es klar da auf beiden Seiten 0 steht. Für p 6 |k folgt es ausEulers Satz und φ(p) = p− 1. ¤Bemerkung 3.23: Der (kleine) Satz von Fermat ist auch die Ausgangsbasis für(probabilistische) Primzahltests. Um zu untersuchen ob 0 < N ∈ Z prim ist, be-rechnet man für zufällige 0 < a < N einfach aN−1 mod N . Falls hier nicht 1 her-auskommt, so ist dies ein Beweis dafür, dass N nicht prim ist. Leider kann man soschlecht beweisen, dass N prim ist. Ein Problem hier sind die Carmichael Zahlen:N ist Carmichael genau dann, wenn für alle ggT(N, a) = 1 auch aN−1 ≡ 1 mod Nfolgt. 561 ist die kleinste Carmichael Zahl.

    Es gibt Varianten hiervon, die”immer“ funktionieren.

  • 14 3. MULTIPLIKATIVE FUNKTIONEN

    Satz 3.24 (Wilson): Eine Zahl p ∈ Z>0 ist genau dann prim, wenn(p− 1)! ≡ −1 mod p

    gilt.

    Bemerkung 3.25: Dies ist (leider) ein sehr schlechtes Kriterium um zu testen obp prim ist: (p− 1)! kann nicht (schnell genug) berechnet werden.

    Beweis. Angenommen, p = ab. Dann gilt a|(p − 1)!, da a ≤ p − 1 also (p − 1)! ≡0 mod a. Andererseits, (p− 1)! ≡ −1 mod p also auch mod a.

    Sei nun p Prim, dann untersuchen wir f(x) := xp−1− 1 ∈ Fp[x]. Nach dem Satz vonEuler/Fermat gilt f(a) ≡ 0 mod p für jedes 0 6= a ∈ Fp. Da aus f(a) = 0 immer(x−a)|f folgt, so gilt ∏0 6=a∈Fp(x−a)|f . Aus Gradgründen (beide Seiten haben Gradp − 1 und sind normiert) folgt dann f = ∏06=a∈Fp(x − a). Speziell können wir unsden konstanten Term ansehen und erhalten −1 ≡ ∏ a ≡ (p− 1)! (mod p). ¤

    Jetzt wollen wir all dies anwenden um die Gleichung

    x2 + y2 = p

    zu untersuchen. Ziel ist der folgende Satz:

    Satz 3.26: Für n ∈ Z>0 sind äquivalent:(1) n = x2 + y2, also n ist Summe von zwei Quadraten.(2) Für p|n und p ≡ 3 mod 4 gilt np(n) ist gerade.

    Lemma 3.27: Seien a, b ∈ Z>0 beide Summen von zwei Quadraten. Dann gilt diesauch für ab.

    Beweis. Sei R := Z[i] := {a + ib|a, b ∈ Z} und i2 = −1 ∈ C. Dann ist R einTeilring von C (AGS) und wir können den komplexen Betrag benutzen. Offenbargilt |a+ ib|2 = (a+ ib)(a− ib) = a2 + b2 und damit ist eine Zahl n > 0 genau dannSumme von zwei Quadraten, wenn es ein x ∈ R gibt mit |x|2 = n. Damit ist dieMultiplikativität klar. ¤

    Bemerkung 3.28: Der Ring R den wir hier benutzt haben, heißt auch Ring derGauß’schen ganzen Zahlen.

    Lemma 3.29 (Thue): Es sei n > 0 kein Quadrat und a ∈ Z beliebig. Dann gibtes ein (0, 0) 6= (x, y) ∈ Z2 mit ax ≡ y mod n und −√n < x, y < √n

    Beweis. Der Beweis benutzt das Schubfachprinzip oder Taubenschlagprinzip.

    Setze A := {(x, y) ∈ Z2 : 0 ≤ x, y < √n} und betrachte die Abbildung α : A →Z/nZ : (x, y) 7→ ax− y. Offenbar gilt #A > (1 +√n− 1)2 = n (1+ kommt von der0, der Rest von x, y <

    √n, also gibt es

    √n > x ≥ √n − 1). Da #Z/nZ = n gilt,

    muss es (x, y) 6= (x′, y′) ∈ A geben mit α(a, x) = α(x′, y′). Also ax − y ≡ ax′ − y′,a(x− x′) ≡ y′ − y und |x− x′|, |y − y′| < √n. ¤

  • 3. MULTIPLIKATIVE FUNKTIONEN 15

    Leider ist der Beweis nicht konstruktiv, dh. wir wissen nicht, wie eine Lösung ge-funden werden kann.Satz 3.30 (Fermat): Für eine ungerade Primzahl p ∈ P sind äquivalent:(1) Es gibt x, y ∈ Z mit x2 + y2 = p(2) Es gibt x ∈ Fp mit x2 ≡ −1 mod p(3) p ≡ 1 mod 4

    Beweis. Wir machen einen Ringschluss:

    1⇒ 3: Sei x2 + y2 = p. Da p ungerade ist, können x und y weder beide gerade nochbeide ungerade sein. ObdA: x ist gerade, y ungerade. Also x = 2k und y = 2l + 1.Damit p = x2 + y2 = 4k2 + 4l2 + 4l + 1 also p ≡ 1 mod 4.3 ⇒ 2: Wir haben p ≡ 1 mod 4 also ist n := (p− 1)/2 gerade. Mit Wilson könnenwir nun schreiben:

    −1 ≡ (p− 1)! mod p =p−1∏

    i=1

    i (mod p)

    ≡n∏

    i=1

    ip−1∏

    i=n+1

    i

    ≡n∏

    i=1

    ip−1∏

    i=n+1

    i− p

    ≡n∏

    i=1

    in∏

    i=1

    −i

    ≡ (−1)nn!2 = n!2Also ist n!2 eine Nullstelle von x2 + 1

    2 ⇒ 1: Sei a mit a2 ≡ −1 mod p gegeben. Nach Thue gibt es dann −√p < x, y < √pmit ax ≡ y mod p. Quadrieren ergibt nun (ax)2 ≡ −x2 ≡ y2 mod p, also x2 + y2 ≡0 mod p, p|(x2 + y2). Wegen x2 + y2 < 2p muss dann p = x2 + y2 gelten. ¤

    Summe von Quadraten. Alles, was noch zu zeigen ist ist die folgende Aussage:Sei n = x2 +y2. Dann gilt für jedes p|n mit p ≡ 3 mod 4: np(n) ∈ 2Z. Angenommen,die Aussage ist falsch. Dann gibt es ein kleinstes n und eine Primzahl p mit np(n)ungerade, speziell p|n und n = x2 + y2. Wir unterscheiden die Fälle p|x und p 6 |x.Für p 6 |x ist x eine Einheit in Fp, also gibt es z ∈ Z mit xz ≡ 1 mod p und damit−1 ≡ (yz)2 mod p. Mit Fermat’s Lemma daher p ≡ 1 mod 4.Falls p|x gilt, so folgt mit p|n auch p|y, aber dann ist auch n/p2 = (x/p)2 + (y/p)2Summe von Quadraten und n war nicht minimal. ¤

    Zum Abschluss dieses Kapitels wollen wir noch zeigen, dass es”viele“ Primzahlen

    p ≡ 1 mod 4 gibt. Ausgangspunkt ist die (triviale) Feststellung, dass für f ∈ Z[t]mit deg f > 0 und k ∈ Z gilt:

    #{r ∈ Z : f(r) = k} ≤ deg f(Dies gilt sicherlich in Q[t] da Q ein

    ”unendlicher“ Körper ist, also auch in Z).

    Satz 3.31: Sei f ∈ Z[x] mit deg f > 0 beliebig. Dann gibt es unendlich vielePrimzahlen p so, dass f ∈ Fp[t] eine Nullstelle hat.

  • 16 3. MULTIPLIKATIVE FUNKTIONEN

    Bemerkung 3.32: Man kann mehr zeigen: die”durchschnittliche“ Anzahl von Null-

    stellen in Fp ist genau die Anzahl der Faktoren über Z, dh. für f =∏l

    i=1 fi erwartenwir l Nullstellen von f modulo

    ”jeder“ Primzahl.

    Beweis. Wir haben f =∑n

    i=0 aixi mit an 6= 0. Falls f eine Nullstelle in Z hat, so

    hat f offenbar eine Nullstelle modulo p für jede Primzahl. Also oBdA, f hat keineNullstelle in Z, damit gilt speziell a0 6= 0.Wir zeigen nun per Induktion, dass es Primzahlen pi (1 ≤ i ≤ n) gibt, so dass f eineNullstelle modulo pi hat. Für i = 0 ist dies trivial. Seien nun p1, . . ., pi gefunden mitf(ri) ≡ 0 mod pi. Dann setzen wir g̃(x) := f(a0x∏ pi) ∈ Z[x]. Dies ist ein Polynomwo jeder Koeffizient durch a0 teilbar ist, damit ist g := g̃/a0 ∈ Z[t] mit konstantemTerm 1. Nach dem Lemma gibt es nun z ∈ Z mit g(z) /∈ {±1, 0}. Also gibt es einePrimzahl q mit q|g(z). Da alle Koeffizienten von g (bis auf den konstanten Term)durch pi Teilbar sind, gilt q 6= pi für alle i. Damit hat f dann ebenfalls eine Nullstellein Fq. ¤

    Korollar 3.33: Es gibt unendlich viele Primzahlen mit p ≡ 1 mod 4

    Beweis. Wende den Satz auf x2 + 1 an. ¤

  • KAPITEL 4

    Kryptographie: RSA

    Die Euler φ Funktion bildet auch die Grundlage für eines der bekanntesten undmeistbenutzten Krypto-Systeme: das RSA Verfahren (nach Rivest, Shamir und Ad-leman die es in 1977 veröffentlicht haben).

    Bob (B) will Alice (A) eine Nachricht schicken und Eve (E) darf sie nicht lesenkönnen. Die Idee ist, dass Bob einfach auf Alice’ Web-Seite geht um Ihren öffent-lichen Schlüssel zu holen. Dieser öffentliche Schlüssel kann von jedem benutzt wer-den um Nachrichten zu schreiben die nur Alice lesen kann - und Eve nicht. DieserSchlüssel kann dan auch benutzt werden um Alices elektronische Unterschrift zuüberprüfen - und all das mit der φ-Funktion.

    Alices öffentlicher Schlüssel besteht aus zwei (großen) Zahlen: (N, e). Bob nimmtseine Nachricht und zerlegt sie in Blöcke (Zahlen) 0 ≤ m < N und berechnets := me mod N . Diese s schickt er dann an Alice.

    Alice hat einen geheimen Schlüssel: d und berechnet jetzt schnell m = sd mod Nund liesst die Nachricht.

    Wie geht das? Und warum? Grundlage ist der folgende Satz - der aus dem Chinesi-schen Restsatz und der φ-Funktion kommt:

    Satz 4.1: Sei N = pq das Produkt zweier Primzahlen p 6= q. Ferner sei 0 < e < Nmit ggT(e, φ(N)) = 1, 0 < d < N mit de ≡ 1 mod φ(N). Dann gilt für jedes0 ≤ m < N : (me)d ≡ m mod N .

    Beweis. Angenommen, ggT(m,N) = 1. Wegen de ≡ 1 mod φ(N) gibt es k ∈ Z mit1 = ef + kφ(N). Wegen ggT(m,N) = 1 folgt m ∈ (Z/NZ)∗ und daher m|(Z/NZ)∗| =mφ(N) ≡ 1 mod N aus Lagrange. Somit (me)d = mde = m1−kφ(N) = m(mφ(N))−k ≡m mod N .

    Falls nun ggT(m,N) = p gilt, so benutzen wir den Chinesischen Restsatz: m ≡0 mod p implizert mef ≡ m ≡ 0 mod p. Wegen q 6 |m folgt wie oben mq−1 ≡ 1 undaus (p−1)(q−1) = φ(N) folgt dann ebenso mde ≡ m mod q. Mit dem ChinesischenRestsatz erhalten wir dann mde ≡ m mod N wie behauptet. Die Fälle ggT(m,N) =q und m = pq werden analog behandelt. ¤

    Um nun das Verfahren zu benutzen geht Alice wie folgt vor: zuerst sucht sie zweiPrimzahlen p 6= q, die etwa 150 Dezimalstellen haben sollten. Als nächstest suchtsie ein e mit ggT(e, φ(N)) = 1 und benutzt dann den Euklidischen Algorithmus umd zu finden. Schliesslich veröffentlicht sie (e,N) und versteckt d.

    Sehr schön, es klappt. Aber was ist mit Eve? Klar ist, dass wenn p und q bekannt sind,Eve sofort d bestimmen und die Nachricht lesen kann. Sie kennt N , also kann sie, imPrinzip, p und q finden. In der Praxis kann sie es jedoch nur (in weniger als einem

    17

  • 18 4. KRYPTOGRAPHIE: RSA

    Jahr), falls pq < 10150 gilt. Für pq ≈ 10300 würde sie viele tausend Jahre und vieletausend Computer benötigen - oder eine neue Idee - oder einen Quantencomputer.Also: es ist nicht bekannt, dass irgend jemand diese RSA-Zahlen zerlegen kann. Aberes gibt auch keinen Beweis, dass es wirklich tausend Jahre dauern würde.

    Zusätzlich muss man noch auf vieles aufpassen:

    • Falls |p− q| zu klein ist, so kann N zerlegt werden• Falls e oder d zu klein sind, so kann m gefunden werden• Falls e klein ist und das selbe e für viele identische Nachrichten benutzt wird

    (Bobs Weihnachtskarten), so kann m gefunden werden• Falls Eve weiß wie Alice Primzahlen sucht kennst sie p und q• Falls Eve Bob Ihren Schlüssel anstellen von Alice’s geben kann, so kann sie m

    lesen.

    Ich bin sicher, es werden noch mehr Einschränkungen gefunden werden...

    In der Kryptographie werden dieses und andere Verfahren näher untersucht.

  • KAPITEL 5

    Primitivwurzeln modulo N

    Hier werden wir uns mit der Einheitengruppe von Z/NZ, also mit (Z/NZ)∗ undihrer Struktur beschäftigen. Es wird sich zeigen, dass ein wesentliches Hilfsmitteldas Polynom f := tm − 1 sein wird. Für jede Nullstelle α von f gilt nun αm = 1,also ist α eine m-te Wurzel von 1, eine Einheitswurzel.

    Definition 5.1: Sei R ein (kommutativer) Ring (mit 1). Ein α ∈ R heißt primi-tive n-te Einheitswurzel, falls αn = 1 und αk 6= 1 für 0 < k < n gilt.Beispiel 5.2: (1) ζn := exp(2πi/n) ∈ C ist eine primitive n-te Einheitswurzel(2) 2 ∈ Z/(2n + 1)Z ist eine 2n-te Einheitswurzel.(3) −1 ist eine 2-te Einheitswurzel in Z, Q und R. (In diesen Ringen gilt auch x

    ist eine n-te Einheitswurzel genau dann, wenn n = 1, 2 und x ∈ {±1} gilt)

    Sei nun ζn eine primitive n-te Einheitswurzel. Setze G := 〈ζn〉, dann gilt für jedesβ ∈ G:

    (1) β = ζkn für 0 ≤ k < n geeignet(2) βn = 1, also ist β eine n-te Einheitswurzel - aber i.Allg. nicht primitiv.(3) Sei β = ζkn. Dann gilt für die Ordnung ord(β), dass ord(β) = n/ ggT(n, k) gilt,

    also ist β eine primitive n/ ggT(n, k)-te Einheitswurzel. Denn: βr = ζkrn unddaher βr = 1 genau dann, wenn n|kr, also r = n/ ggT(k, n).

    (4) ζn ∈ 〈β〉 genau dann, wenn β eine primitive n-te Einheitswurzel ist. Dies istgenau dann der Fall, wenn β = ζkn mit ggT(n, k) = 1 gilt. Die Aussage über dieOrdnung folgt aus dem letzten Punkt. Falls ζn = β

    r = ζkrn so folgt sofort 1 ≡kr mod n. Andererseits, falls ggT(k, n) = 1 gilt, so gibt es s, t mit 1 = sk + tnund damit βs = ζskn = ζ

    1−tnn = ζn.

    (5) Es gibt genau φ(n) viele primitive Einheitswurzeln in G.(6) H := {x ∈ R : xn = 1} also die Menge der Nullstellen von xn − 1 bildet eine

    Gruppe bzgl. der Multiplikation. Ist R ein Körper (oder wenigstens nullteiler-frei), so gilt |H| ≤ n. Achtung: in Z/8Z hat x2 − 1 4 Nullstellen: 1, −1 = 7, 3,5 = −3. Also ist in diesem Fall die Gruppe nicht zyklisch.

    Wie wir gesehen haben, bilden die Einheitswurzeln i.Allg. keine zyklische Gruppe.Um dies besser zu verstehen, werden wir zunächst diese Gruppen genauer untersu-chen.

    Wir fangen mit Z/nZ an.Lemma 5.3: Sei U < Z/nZ eine Untergruppe (additiv). Dann gibt es ein d|nmit U = 〈d + nZ〉 = 〈d̄〉. Andersrum: jedes d|n definiert genau eine Untergruppemittels U := 〈d̄〉.

    19

  • 20 5. PRIMITIVWURZELN MODULO N

    Beweis. Setze π : Z → Z/nZ die kanonische Projektion. Für eine UntergruppeU < Z/nZ betrachten wir π−1(U) < Z (sogar Normalteiler, da Z abelsch ist). Diesist eine Untergruppe von Z, also π−1(U) = 〈d〉 mit d geeignet. Wegen nZ ⊂ π−1(U)folgt dann d|n. Andererseits, jedes d|n definiert eine Untergruppe. ¤Korollar 5.4: Sei G := Z/nZ. Dann hat G für jedes d|n genau eine UntergruppeU := 〈d̄〉. Diese Gruppe hat n/d Elemente und ist zyklisch.Andererseits, eine Untergruppe U < Z/nZ mit n/d Elementen ist von der Form〈d̄〉.Satz 5.5: Sei G eine endliche abelsche Gruppe. Dann sind äquivalent:

    (1) G ist zyklisch(2) Sei k eine Teiler von |G|. Dann hat G genau eine Untergruppe mit k Elemen-

    ten.(3) Sei k eine Teiler von |G|. Dann hat G höchstens eine Untergruppe mit k

    Elementen.(4) Sei k ein Teiler von |G|. Dann hat G höchstens φ(k) Elemente der Ordnung

    k.(5) Sei k ein Teiler von |G|. Dann hat G genau φ(k) Elemente der Ordnung k.

    Damit gilt für jeden Teiler k von |G|, dass U := 〈ζn/k〉 die eindeutige Untergruppemit k Elementen ist. Ferner ist damit jede Untergruppe ebenfalls zyklisch.

    Beweis. 1⇒2: Sei G = 〈ζ〉, und setze ψ : Z → G : n 7→ ζn. Dann gilt kerψ = nZund G ∼ Z/nZ. Nach Korollar 5.4 hat Z/nZ und damit G genau die gefordertenUntergruppen.

    2⇒3: klar3⇒4: Sei k|n beliebig und α ∈ G mit Ordnung ord(α) = k. Dann ist U := 〈α〉 eineUntergruppe mit k Elementen. Da dies für jedes solche α gilt und es maximal einesolche Untergruppe geben kann, müssen alle Elemente β mit ord(β) = d bereits in Uliegen. In U gibt es nun φ(d) viele Elemente der Ornung d, da ord(αk) = d/ ggT(k, d)gilt und diese Elemente in Bijektion zu {0 ≤ k < n| ggT(k, d) = 1} stehen.4⇒5: Wir haben |{α ∈ G| ord(α) = d}| ≤ φ(d) für alle d|n. Mit Lagrange gilt:

    |G| = |⋃d|n{α ∈ G| ord(α) = d}|

    und somit

    n = |G| ≤ ∑d|nφ(d) = n.

    Also muss = gelten.

    5⇒1: G enthält φ(n) > 0 Elemente der Ordnung n. Also gilt G = 〈α〉 für einesdieser α. ¤

    Damit können wir jetzt die Untergruppen der zyklischen Gruppe samt ihren Bezie-hungen einfach charakterisieren:

    Korollar 5.6: Sei G endlich, zyklisch und U , V < G Untergruppen. Dann giltU < V genau dann, wenn |U | ein Teiler von |V | ist.

  • 5. PRIMITIVWURZELN MODULO N 21

    Beweis. Nach Lagrange ist sofort klar, dass U < V auch |U |||V | impliziert. Sei nun|U | =: d|k := |V |. Dann gilt V = 〈v := ζn/k〉 und U = 〈u := ζn/d〉 also vk/d = u undsomit U < V . ¤Bemerkung 5.7: Seien Gi zyklisch. Dann ist ×Gi genau dann zyklisch, wenn die|Gi| paarweise Teilerfremd sind.Denn: falls die |Gi| teilerfremd sind, so folgt aus Gi ∼ Z/|Gi|Z und dem chinesischenRestsatz sofort ×Gi ∼ Z/(∏ |Gi|)Z also ist dies zyklisch. Seien nun die |Gi| nichtkoprim, oBdA: ggT(|G1|, |G2|) = d > 1. Dann gibt es in Gi = 〈ai〉 jeweils φ(d)Elemente der Ordnung d, nämlich a

    j|Gi|/di für ggT(j, d) = 1. Also gibt es in ×Gi

    mindestens φ(d)2 solcher Elemente was nach Satz 5.5 verboten ist.

    Damit können wir nun Fp = Z/pZ besser untersuchen. Es gilt:Satz 5.8: Ist G eine endliche Untergruppe von K∗ wo K ein Körper ist, so ist Gzyklisch.Damit folgt dann (Z/pZ)∗ = 〈a〉 mit einer Primitivwurzel a.

    Beweis. Sei d|#G beliebig und f := td − 1. Da K ein Körper ist und |K| ≥ d gilt,so hat f maximal d Nullstellen und G daher maximal d viele Elemente der Ordnungd. Diese bilden eine Untergruppe, womit G dann zyklisch ist nach Satz 5.5. ¤

    Um nun eine Primitivwurzel der Ordnung d in G zu finden können wir so vorgehen:Wähle a ∈ G zufällig. Teste ord(a) = d. Um ord(a) = d zu testen können wirgeschickter vorgehen, falls wir d =

    ∏pnp(d) kennen. In diesem Fall gilt ord a = d

    genau dann, wenn ad = 1 und ad/p 6= 1 für jedes p|d. In der Praxis ist das Problemdie p|d zu finden.Beispiel 5.9: Wir untersuchen F17 wegen φ(17) = 16 = 24 müssen wir nur a16 = 1und a8 6= 1 testen. Da a16 = 1 automatisch gilt, bleibt a8 = ((a2)2)2 6= 1 zu testen,also 3 Multiplikationen. Versuchen wir a = 2: dann gilt 24 ≡ −1 also 28 ≡ 1 und 2 istnicht primitiv. Wenn wir von Hand rechnen, so folgt damit auch, dass ±2, ±4, ±8±16 nicht primitiv sind. Versuchen wir nun a = 3. Dann gilt 32 ≡ 9, 34 ≡ −4 und38 ≡ −1 also ist 3 primitiv. Wenn wir nachzählen, so sehen wir, dass | < 〈2〉| = 8gilt und wir so acht nicht primitive Elemente haben. Es gibt 16 = 17 − 1 = φ(17)Elemente insgesamt, es muss φ(16) = 8 Primitive geben, also müssen die 8 übrigenprimitiv sein.

    Für p > 1050 kann diese Liste natürlich nicht berechnet werden.

    Lemma 5.10: Sei p ∈ P, k > 0 und a ∈ Z mit ggT(a, p) = 1. Dann gilt entwederord(a+ Z/pk+1Z) = ord(a+ Z/pkZ) oder ord(a+ Z/pk+1Z) = p ord(a+ Z/pkZ).

    Beweis. Wegen pk|pk+1 ist der Ringhomomorphismusπ : Z/pk+1Z→ Z/pZ : x+ pk+1Z→ x+ pkZ

    surjektiv und wohldefiniert, und induziert daher einen offensichtlich surjektivenGruppenhomomorphismus (ebenfalls π genannt) (Z/pk+1Z)∗ → (Z/pkZ)∗. Für denKern erhalten wir sofort | kerπ| = φ(pk+1)/φ(pk) = p. Für die von a erzeugte Unter-gruppe erhalten wir dann ebenfalls, dass

    π̃ : 〈a+ pk+1Z〉 → 〈a+ pkZ〉

  • 22 5. PRIMITIVWURZELN MODULO N

    wohldefiniert und surjektiv mit ker π̃ < kerπ ist und daher ord a+pk+1Z ∈ {ord(a+pkZ), p ord(a+ pkZ)} wie behauptet. ¤

    Damit können wir nun den nächsten Schritt zeigen:

    Lemma 5.11: Seien a ∈ Z, p ∈ P und k > 0 mit pk ≥ 3 und ggT(p, a) = 1.Falls ord(a+ pkZ) = (p− 1)pm und ord(a+ pk+1Z) = (p− 1)pm+1 dann gilt auchord(a+ pk+2Z) = (p− 1)pm+2.

    Beweis. Wir schreiben die Ordnung um: ord(a+ pkZ) = (p− 1)pm heißta(p−1)p

    m ≡ 1 mod pk,also

    a(p−1)pm

    = 1 + bpk

    mit b ∈ Z geeignet. Wegen ord(a+ pk+1Z) = (p− 1)pk+1 kann p|b nicht gelten. Mitdem binomischen Satz folgt nun

    a(p−1)pm+1

    = (1 + bpk)p =p∑

    i=0

    (p

    i

    )bipki = 1 + bpk+1 +

    i>1

    (p

    i

    )bipki + bkpkp

    Wegen p|(

    pi

    )für 1 < i < p und ik ≥ 2k ≥ k + 1 folgt dann

    (pi

    )bipki ≡ 0 mod pk+2.

    Wegen kp ≥ 3 erhalten wir auch kp ≥ k + 2 und somit auch bkpkp ≡ 0 mod pk+2.Also, wenn wir alles zusammensetzen:

    a(p−1)pm+1 ≡ 1 + bpk+1 6≡ 1 mod pk+2,

    also ist die Ordnung modulo pk+1 verschieden von der Ordnung modulo pk+1 unddamit folgt die Behauptung aus dem letzten Lemma. ¤

    Satz 5.12: Sei p ∈ P und a sei primitive Einheitswurzel modulo p. Dann ist aoder a+ p primitiv modulo p2. Insbesondere ist damit (Z/p2Z)∗ immer zyklisch.

    Beweis. Ist a primitiv modulo p, so gilt speziell a ∈ Z/pZ∗ und unser Lemma zeigtord(a + p2Z) ∈ {(p − 1), (p − 1)p}. Angenommen ord(a + p2Z) = p − 1, so folgtap−1 ≡ 1 mod p2. Nehmen wir zusätzlich an ord i((a+ p) + p2Z) = ord(a+ p2Z), sofolgt trivialerweise, dass a+ p primitiv ist modulo p. Probieren wir modulo p2:

    1 ≡ (a+ p)p−1 = ap−1 + (p− 1)pap−2 + p2p−1∑

    i=2

    (p− 1i

    )pi−2ap−1−i

    ≡ ap−1 + (p− 1)pap−2 ≡ 1 + p(p− 1)ap−2 mod p2Aber hieraus würde 0 ≡ p(p−1)ap−2 folgen also p|a was nicht geht. Also war unsereAnnahme falsch und die Behauptung ist richtig. ¤Bemerkung 5.13: Nicht all Z/pkZ sind zyklisch! Es gilt (Z/8Z)∗ = {±1,±3} ={1, 3, 5, 7} und alle Elemente haben Ordnung 2.Beispiel 5.14: 2 ist primitiv modulo 5: 22 = 4 ≡ −1. Modulo 25 erhalten wir210 = (25)2 ≡ 72 ≡ −1 und 24 = 16 6= 1, so dass 2 primitiv ist. Andererseits,probieren wir mal 7: wegen 7 ≡ 2 mod 5 folgt 7 ist primitiv modulo 5. Aber 72 ≡ −1,so dass ord(7 + 25Z) = 4 gilt, also ist 7 nicht primitiv modulo 25. Mit dem Satzfolgt dann sofort, dass 12 = 7 + 5 primtiv ist.

  • 5. PRIMITIVWURZELN MODULO N 23

    Satz 5.15: Sei a primitiv modulo p und p2 für p > 2, p ∈ P. Dann ist a primitivmodulo pk für alle k.

    Beweis. Folgt per Induktion aus Lemma 5.11. ¤

    Was ist jetzt mit 2k?

    Satz 5.16: Für k > 2 gilt ord(5 + 2kZ) = 2k−2 und(Z/2kZ)∗ = 〈−1〉〈5〉 ∼ Z/2Z× Z/2k−2Z.

    Beweis. Der erste Teil ist einfach: ord(5 + 4Z) = 1 = 20, ord(5 + 8Z) = 2 = 21 alsomit Lemma 5.11: ord(5+2kZ) = 2k−2. Zu zeigen bleibt: 〈−1+2kZ〉∩ 〈5+2kZ〉 = 1.Es reicht also −1 + 2kZ 6∈ 〈5〉 zu zeigen. Nehmen wir an, dass es m und b gibt mit

    −1 = 5m + 2kbso folgt sofort −1 = 5m + b2k ≡ 1 mod 4 wegen k > 2. Wenn wir uns jetzt noch dieGruppenordnungen ansehen, so folgt die Behauptung. ¤

    Wenn wir jetzt alles zusammen setzen, so können wir genau klassifizieren wann esprimitive Einheitswurzeln in Z/nZ gibt:Satz 5.17 (Gauß): Sei n > 0 beliebig. Dann gilt

    (Z/nZ)∗ ∼ ∏(Z/pnp(n)|Z)∗

    ist zyklisch genau dann, wenn n ∈ {2, 4, pk, 2pk|2 6= p ∈ P, k > 0} gilt. In diesemFall existieren dann φ(φ(n)) viele primitive Einheitswurzeln.

    Beweis. Wir haben bereits gezeigt, dass (Z/nZ)∗ genau dann zyklisch ist, falls

    (1) (Z/pnp(n)Z)∗ zyklisch ist (für alle p), und(2) die φ(pnp(n)) paarweise teilerfremd sind.

    Damit folgt dann, dass in den angegebenen Fällen die Gruppe zyklisch ist. Wenn wirnun die Gruppe als zyklisch annehmen, so kann es keine zwei verschiedene ungeradePrimzahlen p 6= q|n geben, da φ(p) = p− 1 und φ(q) = q − 1 dann gerade sind undsomit nicht teilerfremd. Ferner hat (Z/2kZ)∗ ungerade Ordnung (1) genau dann,wenn k < 2 gilt und ist zyklisch für k < 3. Der Rest ist dann einfach. ¤

  • 24 5. PRIMITIVWURZELN MODULO N

    1. Quadratische Reste

    Am Anfang haben wir uns mit linearen Gleichungssystemen beschäftigt, später dannmit speziellen quadratischen (Summe von Quadraten) und mit der Einheitengruppevon Z/mZ. Nun wollen wir uns mit dem nächsten Fall beschäftigen: quadratischeGleichungen. Wie wir sehen werden ist es nicht schwierig die Lösbarkeit zu entschei-den, andererseits Lösungen zu finden ist oft (praktisch) unmöglich. Oft (aber nichtimmer) gilt hier auch die pq-Formel, also für

    x2 + px+ q ≡ 0 mod nmit 2 ∈ (Z/nZ)∗ setzen wir D := (p/2)2 − q. Falls es nun y gibt mit y2 ≡ D mod n,so sind −p/2± y Lösungen. Um die abc-Formel für ax2 + bx+ c zu verallgemeinern,muß man mehr aufpassen - i.Allg. dürfen wir durch a nicht Teilen. Ebenfalls der Fall2|n macht Schwierigkeiten, hier gibt es eine etwas andere Theorie, statt y2 = d wirddann y2 + y = d untersucht.

    Mit dem Chinesischen Restsatz gilt nun:

    Lemma 5.18: Sei n =∏pnii und d ∈ Z beliebig. Dann gibt es y mit y2 ≡ d mod n

    genau dann, wenn es yi gibt mit y2i ≡ d mod pnii für alle pi.

    Beweis. Fall es y gibt, so können wir yi := y setzen. Wegen pnii |n folgt dann die

    Behauptung.

    Andererseits, wenn wir die yi haben, so können wir mit dem Chinesischen Restsatzein y finden mit y2 ≡ d mod ∏ pnii = n. ¤

    In der Praxis heißt die leider, dass yi nicht gefunden werden kann, da n i.Allg. nichtfaktoriesiert werden kann . . .. Wir werden sehen, dass es Fälle gibt wo

    ”Wurzelzie-

    hen“ genauso schwer ist wie Faktorisieren - zumindest modulo n. Wurzelziehen in Zist trivial.Lemma 5.19: Sei p ∈ P, k > 0 und a = pmb ∈ Z mit ggT(b, p) = 1. Dann gilt:(1) Für m > k ist x2 ≡ a mod pk immer Lösbar(2) Für 0 ≤ m < k sind equivalent:

    (a) Es gibt y ∈ Z mit y2 ≡ a mod pk(b) 2|m und es gibt y ∈ Z mit y2 ≡ b mod pk−m

    Beweis. Im Fall (1) gilt a ≡ 0 mod n also ist y = 0 Lösung. Im Fall (2) sein nuny2 ≡ a mod pk. Dann folgt pk|y2 − a = y2 − pmb und pk|pm, also pk|y2. Wenn wirjetzt y = plỹ einsetzen mit p 6 |ỹ so sehen wir sofort 2l = m. Andererseits, fallsy2 ≡ b mod pk−m, so folgt ebenfalls y2pm ≡ bpm = a mod n. ¤

    Wir wir sehen reicht es daher sich auf den Fall ggT(a, n) = 1 oder sogar auf den Falln = pk zu beschränken. Die Übung zeigt sogar, dass k = 1 ausreicht.

    Definition 5.20: Sei n > 0 und a ∈ Z mit ggT(a, n) = 1. Die Zahl a heißtquadratischer Rest modulo n, falls es y ∈ Z gibt mit y2 ≡ a mod n. Anderfallsheißt a quadratischer Nichtrest.

    Wie wir sehen werden ist es sehr einfach für Zahlen mit mehreren Tausend Stellenzu entscheiden ob sie quadratische Reste sind - aber oftmals ist es unmöglich eineWurzel zu finden.

  • 1. QUADRATISCHE RESTE 25

    Die Verbindung mit Primitivwurzeln ist sehr eng (Erinnerung: eine Primitivwurzelist eine primitive Einheitswurzel):

    Lemma 5.21: Sei 2 6= p ∈ P, a ∈ Z mit p 6 |a und k > 0. Dann sind äquivalent:(1) a ist quadratischer Rest modulo n(2) Für jede Primitivwurzel b modulo pk gibt es m mit a ≡ b2m mod n(3) Es gibt eine Primitivwurzel b modulo pk und m mit a ≡ b2m mod n(4) ord a+ pk|(p− 1)/2pk−1, also

    a(p−1)/2pk−1 ≡ 1 mod pk

    Damit gilt sofort für jede Primitivwurzel b modulo pk:

    {aist quadratischer Rest} = 〈b2〉

    Beweis. (1) ⇒ (2): Sei y2 ≡ a mod n und b eine Primitivwurzel, also (Z/nZ)∗ =〈b〉. Also gibt es m > 0 mit bm ≡ y mod n, also a ≡ b2m mod n.(2) ⇒ (3): trivial(3) ⇒ (4): Es gilt ord b + pk = φ(pk) und ord b2 + pk = φ(k)/2. Wegen a ∈ 〈b2〉folgt dann die Aussage.

    (4)⇒ (1): Sei b eine Primitivwurzel. Da ord a+pk|1/2 ord b+pk so folgt aus dem Satzüber zyklische Gruppen a ∈ 〈b2〉, also a ≡ b2m mod pk und (bm)2 ≡ a mod pk. ¤

    Mit diesem Lemma und der Übung ist damit das Problem reduziert zu testen ob aquadratischer Rest ist modulo ungerader Primzahlen. Im Prinzip können wir diesmit (4) auch tun, aber für sehr große p ist dies viel zu aufwendig.

    Satz 5.22: Sei p eine ungerade Primzahl. Dann bildet die Menge der quadrati-schen Reste eine Untergruppe von (Z/pZ)∗ und es gibt genau φ(p)/2 = (p− 1)/2quadratische Reste und Nichtreste.

    Beweis. Die Gruppe (Z/pZ)∗ ist zyklisch und daher abelsch, so dassx 7→ x2

    eine Gruppenhomomorphismus ist. Offenbar ist das Bild genau die Menge der qua-dratischen Reste. Da p Prim ist, so hat das Polynom x2 − 1 genau zwei Nullstellen±1 und damit hat der Kern der Abbildung genau zwei Elemente {±1}. Damit folgtder Rest dann aus dem Homomorphiesatz. ¤

    Wie immer, wenn wir nicht weiter kommen geben wir dem Problem einen einfachenNamen:Definition 5.23 (Legendre-Symbol): Sei p eine Primzahl und a ∈ Z beliebig.Wir definieren

    (a

    p

    ):=

    1 a ist quadratischer Rest

    −1 a ist quadratischer Nichtrest0 sonst

    das Legendre Symbol.

    Oft wird auch (a|p) statt(

    ap

    )geschrieben. Unser Ziel ist es nun

    (ap

    )schnell bestim-

    men zu können.

  • 26 5. PRIMITIVWURZELN MODULO N

    Beispiel 5.24: p = 11, also φ(11) = 10 und es sollte 5 quadratische Reste undNichtreste geben. Sammeln wir Quadrate:

    11 = 1, 22 = 4, 32 = 9, 42 = 5, 52 = 3

    dies sind 5 Quadrate, also sind wir fertig.

    a 0 1 2 3 4 5 6 7 8 9 10(a11

    )0 1 -1 1 1 1 -1 -1 -1 1 -1

    Satz 5.25: Sei 2 6= p ∈ P und a ∈ Z. Dann gilt(a

    p

    )≡ a(p−1)/2 mod p

    Beweis. Falls p|a so sind beide Seiten 0. Anderfalls können wir Lemma 5.21.(4)benutzen: Wegen ap−1 ≡ 1 mod p und p Prim folgt a(p−1)/2 ∈ {±1}. Mit Lemma5.21.(4) folgt dann die Behauptung. ¤

    Korollar 5.26: Seien p ∈ P und a, b ∈ Z. Dann gilt:(1) Falls a ≡ b mod p so folgt

    (ap

    )=

    (ab

    ).

    (2) Falls p 6 |a, so folgt(

    a2

    p

    )= 1

    (3) p 6= 2, so gilt (ab

    p

    )=

    (a

    p

    ) (b

    p

    )

    Damit ist Z/pZ → {±1} : a 7→(

    ap

    )eine multiplikative Funktion und ein

    Gruppenhomomorphismus. Speziell sind die quadratischen Reste der Kerndieses Homomorphismuses.

    (4) Für a =∏pnii und p 6= 2 gilt(

    a

    p

    )=

    ∏ (pip

    )ni

    Beweis. (1) und (2) sind klar nach Definition. Für (3) können wir Euler benutzen(ab

    p

    )= (ab)(p−1)/2 = a(p−1)/2b(p−1)/2 =

    (a

    p

    ) (b

    p

    ).

    Der Rest ist dann klar, bzw. folgt per Induktion über die Anzahl der Teiler. ¤

    Damit erhalten wir auch den sog. 1. Ergänzungssatz zum Quadratischen Rezipro-zitätsgetz:

    Korollar 5.27: Sei p ∈ P, dann gilt(−1p

    )=

    1 p = 2

    1 p ≡ 1 mod 4−1 p ≡ 3 mod 4

    Beweis. Für p = 2 klar, sonst beachte, dass (p− 1)/2 gerade ist falls p ≡ 1 mod 4gilt und sonst ungerade ist. ¤

  • 1. QUADRATISCHE RESTE 27

    Für die weiteren Beweise benötigen wir noch ein paar technische Hilfsmittel.

    Definition 5.28: Sei sei 2 6= p ∈ P und k = (p− 1)/2. Dann nennen wir MRp :={−k, . . . , k} die Minimalreste modulo p.Für a ∈ Z mit p 6 |a und 1 ≤ n ≤ (p − 1)/2 gibt es genau ein ra,n ∈ MRp mitna ≡ ra,n mod p. Wir definieren

    ²a,n :=

    1 ra,n > 0

    −1 ra,n < 0und

    νa,p := |{n|²a,n = −1, 1 ≤ n ≤ (p− 1)/2}|Beispiel 5.29: Sei p = 11 und a = 3. Dann gilt zunächst

    MR11 = {−5, . . . , 5}.Ferner gilt

    1 · 3 ≡ 3 ⇒ r3,1 = 3 ⇒ ²3,1 = 12 · 3 ≡ −5 ⇒ r3,2 = −5 ⇒ ²3,1 = −13 · 3 ≡ −2 ⇒ r3,3 = −2 ⇒ ²3,1 = −14 · 3 ≡ 1 ⇒ r3,4 = 1 ⇒ ²3,1 = 15 · 3 ≡ 4 ⇒ r3,5 = 4 ⇒ ²3,1 = 1

    Damit folgt dann ν3,11 = 2.

    Der Sinn dieser Definition liegt z.B. in dem folgenden Lemma:

    Lemma 5.30: Sei 2 6= p ∈ P und p ∈ Z mit p 6 |a. Dann gilt(a

    p

    )=

    (p−1)/2∏

    i=1

    ²a,i = (−1)νa,p

    Beweis. Setze k := (p− 1)/2. Offenbar gilt −na ≡ −ra,n undµa : (Z/pZ)∗ → (Z/pZ)∗ : x 7→ xa

    ist bijektiv da a eine Einheit ist. Damit können wir

    MRp = {ra,n : 1 ≤ n ≤ k}∪̇{−ra,n : 1 ≤ n ≤ k}zeigen (µa ist bijektiv, also kommen alle Reste und alle x ∈ MRp im Bild vor. DieBemerkung mit den Vorzeichen zeigt, dass es eine Symmetrie gibt. Abzählen derMöglichkeiten liefert dann den Rest). Damit folgt dann auch

    {|ra,n| : 1 ≤ n ≤ k} = {1, . . . , k}und damit

    k! =k∏

    n=1

    |ra,n|.Modulo p folgt dann

    k!ak =∏na =

    ∏ra,n =

    ∏ |ra,n|²a,n = k!∏²a,n

    Wegen k < p ist k! eine Einheit, also folgt

    ak ≡k∏

    n=1

    ²a,n

    und die Behauptung aus Satz 5.25 ¤

  • 28 5. PRIMITIVWURZELN MODULO N

    Wenn wir Beispiel 5.29 fortsetzen, so folgt(

    3

    11

    )= ²3,1²3,2²3,3²3,4²3,5 = 1

    Korollar 5.31 (2. Ergänzung): Ist 2 6= p ∈ P, so gilt(

    2

    p

    )= (−1)(p2−1)/8 =

    1 p ≡ ±1 mod 8−1 p ≡ ±3 mod 8

    Beweis. Übung ¤

    Definition 5.32: Sei x ∈ R beliebig. Dann ist bxc := max{z ∈ Z|z ≤ x}die Floor-Funktion. Analog ist dxe := min{z ∈ Z|x ≥ x} die Ceiling-Funktion.Schliesslich definieren wir noch bxe := bx+ 1/2c das

    ”normale“ Runden.

    Definition 5.33: Für 2 6= p ∈ P und a ∈ Z sei

    Sa,p :=(p−1)/2∑

    n=1

    banpc

    Lemma 5.34: Sei 2 6= p ∈ P und a ∈ Z mit ggT(a, z) = 1. Dann gilt(a

    p

    )= (−1)S2a,p

    für ungerades a gilt zusätzlich bereits:(a

    p

    )= (−1)Sa,p

    Beweis. Für den 1. Teil zeigen wir mit Lemma 5.30

    ²a,n = (−1)b2an

    pc

    für 1 ≤ n ≤ (p− 1)/2. Wegen bx+ zc = z + bxc für alle z ∈ Z und x ∈ R giltb2anpc = b2ban

    pc+ 2(an

    p− ban

    pc)c = 2ban

    pc+ b2(an

    p− ban

    pc)c

    Wegen 0 ≤ x − bxc < 1 folgt b2(x − bxc)c ∈ {0, 1}. Speziell erhalten wir 0 genaudann, wenn 2(x− bxc) < 1 also x− bxc < 1/2. Wenn wir dies für x = an

    pbenutzen,

    so sehen wir

    b2anpc = 2ban

    pc

    genau für

    an− pbanpc < p/2.

    Division mit Rest liefert

    an = banpcp+ (an− ban

    pcp)

    Da p/2 6∈ Z ist, so giltan− pban

    pc < p/2 ⇐⇒ ra,n > 0 ⇐⇒ ²a,n > 0

    womit der 1. Teil gezeigt ist.

  • 1. QUADRATISCHE RESTE 29

    Für den 2. Teil berechnen wir für k := (p− 1)/2

    Sa+p,p =k∑

    n=1

    b(a+ p)np

    c =k∑

    n=1

    (banpc+ n)

    = Sa,p +k(k + 1

    2= Sa,p +

    p2 − 18

    Da a ungerade ist, ist p+ a gerade. Damit folgt dann(

    2

    p

    )=

    (a

    p

    )=

    (2a

    p

    )=

    (2a+ 2p

    p

    )=

    (4a+p

    2

    p

    )=

    (4

    p

    ) ( a+p2

    p

    )

    =

    ( a+p2

    p

    )= (−1)Sa+p,p = Sa,p + p

    2 − 18

    Aus Korollar 5.31 folgt dann die Behauptung. ¤

    Damit können wir nun endlich das Quadratische Reziprozitätsgesetz formulierenund beweisen. Für die Entwicklung der Algebra und Zahlentheorie ist dies eine derwichtigsten Aussagen überhaupt: Zusammen mit der Suche nach Fermat’s Satz wardie Verallgemeinerung des Reziprozitätsgesetzes eine der treibended Bestrebungenim 20. Jahrhundert.Satz 5.35 (Quadratisches Reziprozitätsgesetz): Für verschiedene ungeradePrimzzahlen p und q gilt

    (p

    q

    ) (q

    p

    )= (−1) p−12 q−12

    Damit kann(

    np

    )nun einfach berechnet werden - aber zunächst der Beweis:

    Beweis. Mit Lemma 5.34 folgt(p

    q

    ) (q

    p

    )= (−1)Sq,p(−1)Sp,q = (−1)Sq,p+Sp,q

    Also reicht es

    Sq,p + Sp,q =p− 1

    2

    q − 12

    zu zeigen. Dazu definieren wir

    M := {qn− pm|1 ≤ n ≤ (p− 1)/2, 1 ≤ m ≤ (q − 1)/2}Im wesentlichen wollen wir jetzt die Elemente in M zählen um zu zeigen, dass |M | =(p−1)/2(q−1)/2 gilt. Angenommen, wir haben

    ”doppelte“ also qn−pm = qn′−pm′.

    Dann folgt

    p(m−m′) = q(n− n′)mit 0 ≤ |m − m′| ≤ (q − 1) und 0 ≤ |n − n′| ≤ (p − 1), da p 6 |q und 6 |p so folgtq|(m −m′) und daher m = m′. Ebenso n = n′, also hat M keine

    ”doppelten“ und

    daher |M | = (p − 1)/2(q − 1)/2. Analog folgt auch 0 6∈ M da andernfalls pn = qmgelten müßte.

    Als nächstes zerlgen wir M in P und N via

    P := {x ∈M |x > 0} N := {x ∈M |x < 0}.

  • 30 5. PRIMITIVWURZELN MODULO N

    Also x ∈ N genau dann, wenn qn − pm < 0 also n < pm/q gilt. Wegen pm/q 6∈ Zkönnen wir dies verschärfen zu

    1 ≤ n ≤ bpmqc

    Damit können wir N nun disjunkt zerlegen

    N =⋃̇(q−1)/2

    m=1{qn− pm|1 ≤ n ≤ bpm

    qc}

    Dies liefert sofort |N | = ∑bpmqc = Sq,p. Analog erhalten wir |P | = ∑b qnp c = Sp,q und

    damit die Behauptung. ¤

    Beispiel 5.36: Wir wollen(

    62131

    )berechnen. Zunächst sehen wir 62 = 2 · 31, so

    dass wir(

    2131

    )und

    (31131

    )brauchen. Der 1. Faktor ist einfach, der 2. erfordert mehr

    Arbeit:(

    31

    131

    )= −

    (131

    31

    )= −

    (7

    31

    )=

    (31

    7

    )=

    (3

    7

    )= −

    (7

    3

    )= −

    (1

    3

    )= −1

    Damit haben wir insgesamt(

    62131

    )berechnet und wissen, dass es x geben muss mit

    x2 ≡ 62 mod 131. Leider können wir es nicht einfach berechnen.”Raten“ (Compu-

    ter) liefert x = 18 und x = 113 als Lösungen.

    Ein Problem mit der Rechnung im Beispiel ist die Faktorisierung. Um diese zuUmgehen führer wir das Jakobi-Symbol ein:

    Definition 5.37: Sei n eine Ungerade Zahl, n =∏pnii und a ∈ Z beliebig. Dann

    ist (a

    n

    ):=

    ∏ ( api

    )n

    i

    wobei noch(

    ap

    )= 0 gesetz wird falls p|a gilt.

    Damit stimmen Jakobi und Legendre Symbole überein - falls n eine ungerade Prim-zahl ist. Das Jakobi Symbol hat nun fast die selben Eigenschaften wir das LegendreSymbol und kann nun immer ohne Faktorisierung berechnet werden. Speziell gilt(Übung):

    (1) Für a ≡ b mod c gilt(

    ac

    )=

    (bc

    )

    (2)(−1c

    )= (−1)(c−1)/2

    (3)(

    ab

    ) (bc

    )=

    (abc

    )

    (4)(

    ab

    ) (ac

    )=

    (abc

    )

    (5)(

    ab

    ) (ba

    )= (−1)(a−1)/2·(b−1)/2

    (6)(

    2b

    )= (−1)(b2−1)/8

    Achtung: hier gilt i. Allg. nicht, dass a ein quadratischer Rest ist modulo b falls(

    ab

    )=

    1 gilt. Damit ist die Berechnung von(

    ab

    )so kompliziert wie eine ggT berechnung

    mit dem euklidischen Algorithmus: eine Kette von Divisionen mit Rest.

  • 1. QUADRATISCHE RESTE 31

    1.1. Rabin-Cryptosystem. Seien p, q Primzahlen mit p, q ≡ 3 mod 4 und N :=pq. Eine Nachricht 0 ≤ P < N wird nun als

    C := P 2 mod N

    verschlüsselt.

    Zum entschlüsseln brauchen wir den Chinesischen Restsatz und das folgende Lemma,was in der Übung bewiesen wurde:

    Lemma 5.38: Sei p ≡ 3 mod 4 eine Primzahl, 0 ≤ a < p und b := a(q+1)/4. Danngilt b2 ≡ a mod p.Also berechnen wir Cp := C mod p und Cq := C mod q. Dann wird das Lemmabenutzt um bp, bq mit b

    2p ≡ Cp mod C und b2q ≡ Cq mod q zu finden. Schliesslich wird

    der Chinesische Restsatz eingesetzt um ±bp, ±bq zu kombinieren um Pi (1 ≤ i ≤ 4)mit P 2i ≡ C mod N zu erhalten. Die gesuchte Nachricht ist nun ein Pi.Beispiel 5.39: p = 7, q = 3 also N = 21. Wir wollen P = 11 verschlüsseln.

    P 2 = 121 ≡ 16 mod N.

    Zum entschlüsseln berechnen wir 16 ≡ 1 mod 3 und 16 ≡ 2 mod 7 also sind ±1 mod3 und ±4 mod 7 die möglichen Wurzeln.Für den Chinesischen Restsatz berechnen wir 1 = 5 · 3 − 1 · 7 und dann (1)(−7) +(4)(15) = 11 mod 21, (−1)(−7)+(4)(15) = 4 mod 21, (1)(−7)+(−4)(15) = 10 mod21 und (−1)(−7) + (−4)(15) = 17 mod 21.

    Dieses Verfahren hat den Nachteil, dass wir entscheiden müssen welche der 4 Möglich-keiten korrekt ist. Aber es hat einen Vorteil gegenüber RSA:

    Satz 5.40: Wenn wir das Rabin Cryptosystem brechen können, so können wir Nfaktorisieren: angenommen, wir haben N und 0 ≤ C < N und können P := {a2 ≡C mod N} finden, so können wir auch p, q mit N = pq berechnen.

    Beweis. Sei X 6= ±Y ∈ P . Dann gilt X2 ≡ Y 2 mod N , also N |(X2 − Y 2) =(X+Y )(X−Y ). Angenommen, ggT(X+Y,N) = N . Wegen X+Y < 2N folgt dannN = X + Y , also X = −Y mod N was wir ausgeschlossen haben. Analog folgt ausggT(X − Y,N) = 1 dann ggT(X + Y,N) = N . Also muss ein ggT nicht-trivial sein.Wegen N = qp gilt ggT(Pi, N) ∈ {1, p, q, N} aosl können wir N faktorisieren. ¤

    Damit ist das Brechen des Rabin-Systems equivalent zum Faktorisieren - eine Aus-sage die für das eng verwande RSA-System unbekannt ist! Theoretisch ist es damitdann auch sicherer als RSA, hat jedoch das Problem, dass wir 4 mögliche Nachrich-ten erhalten und die korrekte heraussuchen müssen.

    Es gibt Ansätze das Rabin-System eindeutig zu machen, dann verlieren wir jedochdie Äquivalenz zur faktorisierung.

    Eine andere formulierung währe etwa so: angenommen, wir haben eine Funktion dieirgendwie eine Wurzel modulo N berechnet. Dann wählen wir zufällig 0 < m < N ,berechnen e = m2 mod N und suchen dann mit der Annahme eine Wurzel w. Da es4 gibt, so werden wir (früher oder später) w 6= ±m haben. Wie in dem Satz obenerhalten wir dann eine Faktorisierung.

  • 32 5. PRIMITIVWURZELN MODULO N

    1.2. Das Quadratische Sieb. Die Idee, aus X2 ≡ Y 2 mod N eine Faktorisie-rung zu erhalten ist der zentrale Gedanke in allen modernen Faktorisierern (mit derAussnahme von ECM). Hier werden wir uns die einfachste Variante des quadrati-schen Siebes ansehen.

    Wir wollen N zerlegen. Dann wählen wir eine endliche Menge B ⊂ P von Primzah-len - genau wie viele hängt von der Größe von N ab. Als nächstes berechnen wirm := b√Nc und für 0 < i < c berechnen wie ri von (i + m)2 mod N . Falls in derFaktorisierung von ri nur Primzahlen in B auftauchen, so merken wir uns i und dieFaktorisierung von ri.

    Beispiel 5.41: Sei N = 2279. Wir wählen B = {2, 5, 7, 13, 17} und berechnenm = 47. Für c = 20 testen wir die ri und finden:

    i Faktorisierung1 52

    3 13 · 175 52 · 177 72 · 1316 2 · 5 · 13220 2 · 5 · 13 · 1736 22 · 13

    Hier sehen wir (m1)2−N = 25 und ggT(m1 + 5, N) = 53. Wir

    können jetzt noch andere quadrate bauen und testen: Wenn wir r5, r16, r20 und r36multiplizieren, so erhalten wir ein Quadrat.

    Also X := r5r16r20r36 mod N = 1789 und Y := 22 · 52 · 132 · 17 mod N = 146 und

    ggT(X + Y,N) = 43, ggT(X − Y,N) = 53ist die Faktorisierung.

    Andererseits: r3r5r7 mod N = 1381, 5 · 7 · 13 · 17 mod N = 898 aber hier sind beideggTs trivial.

    Aber: wir haben ganz viel faktorisiert um die Tabelle aufzubauen. Hier benutztman nun das sog. sieben. Die Grundidee ist, dass falls (i + m)2 − N durch p ∈B teilbar ist, so gilt dies auch für (i + p + m)2 − N . Wir notieren dies in einerTabelle. i 1 2 3 4 5 6 7 . . . Nun berechnen wir Nullstellen von (x+m)2−N modulo p = 2 und erhalten eine doppelste Nullstelle bei x = 0, also ist r0, r2, r4,. . . durch 2 Teilbar:

    i : 1 2 3 4 5 6 7 . . .2 0 2 0 2 0 2 0 . . .

    Nun für p = 5. Wir erhalten Nullstellen 0, 1:

    i : 1 2 3 4 5 6 7 . . .2 0 2 0 2 0 2 0 . . .5 0 5 0 0 5 5 0 . . .

    Nun für p = 7. Wir erhalten Nullstellen 0, 4:

    i : 1 2 3 4 5 6 7 . . .2 0 2 0 2 0 2 0 . . .5 0 5 0 0 5 5 0 . . .7 0 0 0 7 0 0 7 . . .

  • 1. QUADRATISCHE RESTE 33

    Und so weiter. Spalten mit vielen Einträgen sind dann wahrscheinlich komplettfaktorisiert und wir testen diese weiter. In der Praxis geht man etwas anders vor,hier wird die Tabelle mit log ri initialisiert und dann log p abgezogen. Einträge dieam Ende (fast) Null sind, werden dann weiterverarbeitet. Oft wird daher auch p =4, 8, 9, 16 zugelassen.

    Alle modenren Verfahren (QS, MPQS, NFS, GNFS) benutzen diese Grundstategie.Sie unterscheiden sich in der Wahl des oder der Polynome mit denen gesiebt wird.

  • KAPITEL 6

    Quadratische Zahlkörper

    Wir haben schon mehrfach quadratische Gleichungen betrachtet, bzw diese sind unsbegegnet. Ein zentrales Problem bisher war die Lösbarkeit zu untersuchen, bzw.Lösungen zu finden. Jetzt werden wir uns der anderen Seite zuwenden, d.h. wiruntersuchen nicht-lösbare Gleichungen.

    Im weiteren sei D eine ganze Zahl die kein Quadrat in Z ist, also ist speziell x2−D =0 nicht lösbar in Z (aber natürlich in C).Definition 6.1: Sei D ∈ Z \ {0} kein Quadrat. Dann heißt

    Q[√D] := {a+ b

    √D|a, b ∈ Q}

    ein quadratischer Zahlkörper. Für D < 0 heißt er imaginär-quadratisch, sonstreell-quadratisch.

    Bemerkung 6.2: Hier verstehen wir√D als ein Objekt (Zahl?) mit der Eigen-

    schaft, dass (√D)2 = D gilt. Im Allgemeinen werden wir nicht annehmen, dass

    √D

    reell oder komplex ist. (So wie i ∈ C auch eingeführt wird)

    Lemma 6.3: Sei D ∈ Z \ {0} kein Quadrat. Dann istQ[√D] := {a+ b

    √D|a, b ∈ Q}

    ein Körper. Speziell gilt:

    (1) (a+ b√D) + (c+ d

    √D) := (a+ c) + (b+ d)

    √D

    (2) (a+ b√D)(c+ d

    √D) := (ac+ bdD) + (ad+ bc)

    √D

    (3) (a+ b√D)−1 = (a− b√D)/(a2 − b2D)

    Damit gilt dann Q[√D] ' Q[t]/(t2 −D)

    Beweis. Zu zeigen ist, dassQ(√D) mit den angegebenen Operationen einen Körper

    bildet, aber dies kann leicht nachgerechnet werden. Der letzte Teil folgt dann auto-matisch. ¤

    Definition 6.4: Sei K := Q[√D] eine Zahlkörper, dann ist

    (.) : K → K : a+ b√D 7→ a− b

    √D

    ein Q-Automorphismus von K.

    Beweis. Zu zeigen ist nur, dass (a+ b√D)(c+ d

    √D) = (a+ b

    √D)(c+ d

    √D) gilt.

    Aber das folgt durch ausmultiplizieren. ¤35

  • 36 6. QUADRATISCHE ZAHLKÖRPER

    Lemma 6.5: Sei K ein quadratischer Zahlkörper. Für jedes x ∈ K definieren wirdie Spur (trace) Tr(x) := x+ x und die Norm N(x) := xx ∈ Q. Dann gilt:(1) Tr(x), N(x) ∈ Q(2) Tr ist Q-linear: Tr(ax+ by) = aTr(x) + bTr(y) für a, b ∈ Q und x, y ∈ K(3) N ist multiplikativ: N(xy) = N(x) N(y)(4) Tr a = 2a, N(a) = a2 für a ∈ Q

    Beweis. Einsetzen und nachrechnen. ¤Satz 6.6: Sei K ein quadratischer Zahlkörper und x ∈ K. Setze f := t2−Tr(x)t+N(x) ∈ Q[t]. Dann gilt f(x) = 0.

    Beweis. Nachrechnen: (t− x)(t− x̄) = t2− t(x+ x̄) + xx̄ = t2−Tr(x)t+ N(x) ¤

    Im weiteren würder wir gerne wieder Ringe betrachten, da Teilbarkeit, irreduzibilitätund ähnliches in K nicht interessant sind. Wir haben einen offensichtlichen Ring:

    Z[√D] := {a+ b

    √D : a, b ∈ Z} ⊆ Q[

    √D]

    Wenn wir uns die Operationen in K ansehen, so ist Z[√D] offenbar ein Teilring.

    Wir sehen auch, dass Tr : Z[√D] → Z und N : Z[

    √D] → Z gehen.

    Andererseits, für D = 5 gilt Tr(1 +√

    5)/2 = 1 und N(1 +√

    5)/2 = −1, also gibt es”nicht ganze“ Zahlen die ganze Norm und Spur haben. Dies ist unschön. Um dies

    in den Griff zu bekommen bzw. zu untersuchen, setzen wir

    ωD :=

    √D D 6≡ 1 mod 4

    1+√

    D2

    D ≡ 1 mod 4Bemerkung 6.7: Sei R ⊆ S komutative Ringe und ω ∈ S Nullstelle von f ∈ R[t].Dann ist R[ω] := Imφ für φ : R[t] → S : g 7→ g(ω) ein Teilring von S. Ist f normiert,so gilt R[ω] = {∑deg f−1i=0 aiωi : ai ∈∈ R}. (Wenn f normiert ist, so können wir jedesPolynom g ∈ R[t] als g = qf + r schreiben mit q,r ∈ R[t] und deg r < deg f . Damitfolgt dann die Aussage)

    Lemma 6.8: Z[ωD] := {a + bωD : a, b ∈ Z} ist ein Teilring von K = Q[√D] der

    Z[√D] enthält.

    Beweis. Nur für D ≡ 1 mod 4 ist hier noch was zu zeigen. Mit Satz 6.6 folgtω2D−ωD +NωD = 0, also Z[ωD] ⊂ Q[

    √D] ein Ring. Wegen

    √D = 2ωD− 1 ist dann

    auch die andere Inklusion klar. ¤Beispiel 6.9: (1) D = −1: aus den Grundlagen wissen wir i2 = −1 für i ∈ C.

    Damit Z[i] = {a+ bi : a, b ∈ Z} ist der Ring dar Gaußschen ganzen Zahlen.(2) D = −3, ζ3 := (−1 +

    √−3)/2 = (−1 + i√3)/2. Dann gilt ζ33 = 1 und Z[ζ3] istder Ring der Eisensteinschen ganzen Zahlen. Hier gilt Z[

    √−3] 6= Z[ζ3].(3) Z[

    √5] = {a+ b√5} 6= Z[ω5] = {a+ bω5}

    Lemma 6.10: Sei K ein quadratischer Zahlkörper. Dann ist K ein Q-Vektorraumder Dimension 2 mit Basis {1,√D}.

  • 6. QUADRATISCHE ZAHLKÖRPER 37

    Beweis. Was noch zu zeigen ist, ist die lineare Unabhängigkeit von 1 und√D.

    Angenommen, diese sind Q-linear abhängig, so gibt es a, b ∈ Q mit a + b√D = 0,also

    √D = −a/b und damit D = a2/b2 im Widerspruch zu D kein Quadrat. ¤

    Damit sehen wir auch:

    Bemerkung 6.11: K quadratischer Zahlkörper, dann ist {x ∈ K : x̄ = x} = Q.Bemerkung 6.12: Sehen wir uns die Vektorraum-Struktur noch mal an. Insbeson-dere die Abbildung: φx : K = Q2 → K = Q2 : y 7→ xy. Dies ist sicherlich eineQ-lineare Abbildung: φx(ay + bz) = xay + xbz = aφx(y) + bφx(z). Also hat dieseAbbildung eine Matrix-Darstellung bzgl. der Basis 1,

    √D. Dazu berechnen wir für

    x = a+ b√D nur φx(1) = x und φx(

    √D) = a

    √D + bD, also erhalten wir

    Mx =

    (a bDb a

    ).

    Für die Spur und Determinante von Mx gilt nun TrMx = Trx und detMx = N(x).Ferner ist das charakteristische Polynom von Mx genau das Polynom was wir obenschon einmal gesehen haben.

    Definition 6.13: Eine Zahl x heißt ganz algebraisch (über Z) falls es ein nor-miertes Polynom f ∈ Z[t] gibt mit f(x) = 0.

    Wie wir oben gesehen haben, so gilt für quadratische Zahlkörper sogar: x ∈ K istganz algebraisch genau dann, wenn Tr x und N x ∈ Z sind. (Angenommen, x istganz algebraisch. Dann haben wir ein normiertes Polynom f ∈ Z[t] mit f(x) = 0.Zusätzlich haben wir auch g := t2 − tTr(x) + N(x) ∈ Q[t] mit g(x) = 0. Also isth := ggT(f, g) ein 3. Polynom mit dieser Eigenschaft. Wegen f normiert und h|ffolgt dann h ∈ Z[t] (ein Lemma von Gauß). Falls deg h = g so muss nun auchg ∈ Z[t] gelten. Andernfalls, deg h = 1, aber dann x ∈ Z und g ∈ Z[t]).Bemerkung 6.14: Sei D = m2R mit R kein Quadrat. Dann gilt Q[

    √D] = Q[

    √R].

    Denn (m√R)2 = D, also

    √D = m

    √R, damit können wir dann

    φ : Q[√D] → Q[

    √R] : a+ b

    √D 7→ a+ bm

    √R

    definieren. Dies ist ein Isomorphismus wie wir einfach nachrechnen können.

    Für dieQ-Vektorraumstruktur ist dies nur ein Basiswechsel, also bleiben damit Spur,Norm und das Polynom ungeändert.

    Definition 6.15: Eine ZahlD ∈ Z heißt quadratfrei, falls ausm2|D stetsm = ±1folgt.

    Satz 6.16: Sei D 6= 1 quadratfrei. Dann ist{x ∈ K =

    √D : x ist ganz algebraisch} = Z[ωD]

    Speziell bilden die ganzen Zahlen einen Teilring von K den wir auch den ganzenAbschluss von Z[

    √D] in K nennen.

    Gebräuchlich sind auch Z[ωD] = ZK = OK , Ring der ganzen Zahlen, Ganzheits-ring oder Maximalordnung.

  • 38 6. QUADRATISCHE ZAHLKÖRPER

    Beweis. Sei x = a + b√D ganz algebraisch und D quadratfrei. Dann gilt Tr x =

    2a ∈ Z, also a ∈ Z/2. Aus Nx = a2−b2D ∈ Z folgt dann sofort auch b ∈ Z/2. Setzenwir nun ã = 2a und b̃ = 2b, damit ã2 + b̃2D = 4 Nx. Angenommen ã ≡ 0 mod 2,dann folgt (ã)2 ≡ 0 mod 4. Da D quadratfrei ist, so folgt D 6≡ 0 mod 4, also muss b̃dann auch gerade sein, und x ∈ Z[√D].Sei nun ã ≡ 1 mod 2. Für c ∈ Z gilt z2 ≡ 0, 1 mod 4. Falls nun D ≡ 2, 3 mod 4 gilt,so folgt aus ã2−Db̃2 = 4 Nx ≡ 0 mod 4 sofort D ≡ 1 mod 4 und b̃ ≡ 1 mod 2. Damitfolgt dann x = (2a′+1)/2+(2b′+2)/2

    √D = ((2b′+1)ωD)−(2b′+1)/2+(2a′+1)/2.

    Wegen (2b′ + 1)/2− (2a′ + 1)/2 = b′ − a′ ∈ Z folgt dann die Behauptung. ¤

    Dieser Beweis hat einen”Schönheitsfehler“, er klappt leider nur für quadratische

    Körper. Im Allgemeinen gilt (gegenstand der Zahlentheorie) immer noch, dass dieganzen Zahlen einen Ring bilden. Der Beweis kann dann nur die Polynome benut-zen...

    Von einem praktischen Standpunkt können wir hier schon sehen, was auch im All-gemeinen richtig ist: ganze Abschlüsse brauchen faktorisierung - wie sonst sollen wirD quadratfrei testen?

    Damit können wir die quadratischen Gleichungen vom Anfang des Semesters wiederaufgreifen:

    x2 + y2 = p

    ist genau dann lösbar, wenn es α ∈ Z[i] gibt mit Nα = p. Wie wir gesehen haben,ist dies äquivalent zu

    p2 ≡ 1 mod 4und zu (−1

    p

    )= 1.

    Als nächstes wollen wir uns mit Einheiten in Z[ωD] beschäftigen. Dies ist motiviertvon der Untersuchung von

    x2 +Dy2 = 1

    Satz 6.17: Sei D 6= 1 kein Quadrat. Dann istZ[ωD]∗ = {x ∈ Z[ωD]|N(x) = ±1}

    die Gruppe der Einheiten in Z[ωD].

    Beweis. Sei x eine Einheit in Z[ωD], so gibt es ein y ∈ Z[ωD] mit xy = 1, also auchN(xy) = N(x)N(y) = 1. Da die Norm N : Z[ωD] → Z geht, folgt N(x) = ±1.Andererseits, N(x) = 1, dann gilt xx̄ = N(x) = ±1, also ist entweder −x̄ oder xdas Inverse. Es ist klar, dass x̄ ∈ Z[ωD] gilt. ¤Bemerkung 6.18: Sei D < 0 kein Quadrat. Dann ist die Menge

    {x ∈ Z[√D]|N(x) = k}

    für alle k ∈ Z endlich. Damit ist dann auch{x ∈ Z[

    √D]|N(x) ≤ k}

    endlich, da hier N(x) ≥ 0 gilt.

  • 6. QUADRATISCHE ZAHLKÖRPER 39

    Korollar 6.19: Es gilt

    Z[√−1]∗ = {±1,±i = √−1}

    Z[√−3]∗ = {±1,±ω−3,±ω2−3}

    undZ[√D] = {±1}

    für jedes quadratfreie D < 0.

    Das entsprechende Ergebnis für D > 0 ist komplizierter:

    Satz 6.20: Sei D > 0 keine Quadrat. Dann gibt es eine Einheit ² ∈ Z[ωD] mitZ[ωD]∗ = {±²r|i ∈ Z}

    speziell ist hier die Einheitengruppee unendlich - und fast zyklisch.

    Der Beweis ist komplizierter und erfordert mehrere Schritte.

    Bemerkung 6.21: Für jedes x ∈ Z[ωD] gilt N(x)/x ∈ Z[ωD] ”jedes Element teiltseine Norm“. Wegen N(x) = xx̄ ist dies hier trivial.

    Lemma 6.22: Sei c ∈ N und αi ∈ Z[ωD] mit N(αi) = c paarweise verschieden.Dann gibt es i 6= j mit αi/αj ∈ Z[ωD], damit ist dann αi/αj eine Einheit.

    Beweis. Wir definieren eine Äquivalenzrelation: α ≈ β genau dann, wenn α− β ∈cZ[ωD]. Wegen Z[ωD] = Z + ZωD hat Z[ωD]/ ≈ maximal c2 viele Elemente, alsomuss es αi 6= αj geben mit αi − αj = cγ für ein geeignetes γ. Jetzt gilt aber

    α

    β=α− β + β

    β=c

    βγ + 1 =

    N(β)β

    γ + 1 ∈ Z[ωD]

    Analog zeigen wir auch βα∈ Z[ωD] also ist der Quotient eine Einheit. ¤

    Der schwierige Rest von dem Beweis besteht nun darin, eine unendliche Folge vonsolchen αi mit beschränkter Norm zu finden. Hierzu werden wir Einbettungen nachR betrachten, dafür sei R 3 sD > 0 mit s2D = D gegeben.Lemma 6.23: Es gibt eine Folge αn = xn+yn

    √D mit yn ≤ n und |xn−ynsD| ≤ 1/n

    Beweis. Setze ri := isD − bisDc, für 0 ≤ i ≤ n so ist ri ∈ [0, 1[. Das HalboffeneIntervall [0, 1[ kann disjunkt zerlegt werden

    [0, 1[=⋃̇

    [j

    n,j + 1

    n[

    (0 ≤ j < n). Da wir n viele kleine Intervalle haben, aber n + 1 ri’s, so muss esri 6= rj geben mit ri, rj ∈ [ kn , k+1n [ für ein geeignetes k. Wir Zeigen nun: αn :=(i − j)√D + (bisDc − bjsDc) leistet das gewünschte. Die Abbildung φ :

    √D 7→ sD

    leistet φ(ᾱn) = ri − rj, und |ri − rj| < 1/n. Damit folgt dann i − j ≤ n und|φ(ᾱn)| = |xn − ynsD| < 1/n wie Behauptet. ¤Lemma 6.24: Für die oben konstruierte Folge gilt

    N(αn) ≤ 1 + 2sD

  • 40 6. QUADRATISCHE ZAHLKÖRPER

    Beweis. Dies ist nun Einfach:

    N(αn) = αnᾱn = |φ(αn)||φ(ᾱn)|Aber |φ(ᾱn)| ≤ 1/n und

    αn = ᾱn + 2yn√D

    was sofort|φ(ᾱn)| ≤ 1/n+ 2nsD

    zeigt, da yn ≤ n nach Konstruktion. ¤

    Jetzt halten wir noch schnell fest, dass αi 6= 0 ist, damit können wir dann eineTeilfolge mit paarweise verschiedenen αik auswählen: i1 := 1 und finde dann i2 mitφ(ᾱi2) ≤ 1/i2 < φ(ᾱi1). Induktiv erhalten wir so eine Folge paarweise Verschiedenerαi mit beschränkter Norm. Nach unserer Bemerkung muss es daher Indizies i 6= jgeben mit ² := αi/αj ist eine Einheit. Da, nach Konstruktion, φᾱi ↘ 0, strengmonoton, so ist der Quotient nicht −1. Speziel, 0 < φ²̄ < 1, so dass ²i = ²j giltgenau dann, wenn i = j. Also haben wir unendlich viele Einheiten gefunden!

    Was noch fehlt um die Einheitengruppe vollständig zu verstehen ist die Beobachtung,dass die Gruppe im wesentlichen Zyklisch ist:

    Lemma 6.25: Seien a, b ∈ Z[√D]∗ Einheiten. Dann gibt es i, j ∈ Z mit aibj = 1.

    Beweis. Wir betrachten die Abbildung L : Z[√D]∗ → (R2,+) : ² = x + y√D 7→

    (log |x+ ysD|, log |x− ysD|)Dann gilt:

    (1) L(ab) = L(a) + L(b)(2) L(a) ∈ {(x, y) ∈ R2|x+ y = 0}(3) L(a) = 0 genau dann, wenn ak = 1 für k > 0 gibt.

    (1) und (2) sind klar, für (3) gilt: L(a) = 0 genau dann, wenn |x± ysD| = 1, damiterhalten wir sofort, dass aus ak = 1 immer L(a) = 0 folgt. Für die andere Richtungbetrachten wir A := {ak : k > 0}. Hier gilt nun L(b) = 0 für alle b ∈ A. Für diePolynome f(t) := t2 − Tr(b)t + N(b) folgt |Tr(b)| ≤ 2 und |N(b)| = 1, damit gibtes nur endlich viele solcher Polynome, die daher nur endlich viele Nullstellen habenkönnen. Also muss die Menge B endlich sein, und damit gibt es so ein k.

    Setzen wir nun aR := L(a) und bR := L(b), so folgt aus (2) sofort, dass es u, v ∈ Rgibt mit uaR + vbR = 0. OBdA, u 6= 0, da es nach (3) sonst ein i > 0 gibt, sodass j = 0 eine Lösung ist. Dann gilt aR = −v/ubR. Wählen wir jetzt r, s ∈ Z mit|r/s− v/u| < 1/s. so gilt‖saR+rbR‖ ≤ s‖aR+r/sbR‖ ≤ s‖aR+(r/s−v/u)bR+v/ubR‖ = s‖(r/s−v/u)bR‖ ≤ ‖bR‖Indem wir s induktiv wählen, erhalten wir so eine unendliche Folge von Elementenasibri mit beschränkten Logarithmen, also auch φ() und φ(̄) beschränkt. Wie in demBeweis von (3) betrachten wir wieder die Polynome mit Koeffizienten Tr und N. Ausber Beschränkheit von φ und φ̄ folgt das Tr und N ebenfalls beschänkt sind, alsohaben diese unendlich vielen Elemente nur endlich viele Polynome. Dies kann nichtgehen, also muss u/v ∈ Q sein und die gesuchten i, j sind trivial zu finden. ¤

  • 6. QUADRATISCHE ZAHLKÖRPER 41

    Damit können wir jetzt die Einheitengruppe komplettieren:

    Satz 6.26: Es gibt genau eine Einheit ² mit Z[√D]∗ = {±²i : i ∈ Z} mit φ(²) > 1.

    Beweis. Wir haben gesehen, dass es Einheiten α gibt so, dass αi eine unendlicheMenge bildet. Sei nun ² darunter so gewählt, dass φ(²) > 1 minimal ist. Da Lemmavon oben zeigt, dass dann jede weitere Einheit eine Potenz hiervon sein muss. Eineunendliche zyklische Gruppe (Z[

    √D]∗/− 1) hat genau 2 Erzeuger, also können wir

    den mit φ > 1 wählen. ¤

    Die Einheit im dem Satz heißt auch Fundamentaleinheit. Im Prinzip können wir siewie in dem Algorithmus berechnen, dies ist jedoch nicht effizient, diese Einheitenwerden zu gross. Man kann zeigen, dass die Fundamentaleinheit in Z[

    √D] maximal

    O(exp(sD)) viele Stellen benötigt. Es gibt Beispiele wo man dies sieht: D = 100001oder D = 1000099 z.B. brauchen 110 bzw > 1000 viele Ziffern.

    Um damit besser arbeiten zu können müssen wir uns noch mit der Primfaktorzerle-gung beschäftigen.

    Bemerkung 6.27: In der AGS haben wir euklidische Ringe betrachtet: Ein kom-mutativer Ring R heißt euklidisch, wenn es eine euklidische Funktion ν : R\{0} → Ngibt, so dass es für alle a, b ∈ R, b 6= 0 ein q und r gibt mit

    a = qb+ r

    und r = 0 oder ν(r) < ν(b). Also gibt es in euklidischen Ringen immer eine Divisionmit Rest.

    Ein Integritätsring R heißte faktoriell (oder ZPE), falls jedes 0 6= x ∈ R eine Darstel-lung als Produkt von Primelementen hat. Diese ist dann im wesentlichen eindeutig.

    Wir haben ebenfalls nachgeweisen, dass jeder euklidische Ring ZPE ist.

    Wir werden jetzt der Frage nachgehen, ob unsere neuen Ringe ebenfalls euklidischsind.Wir haben ja bereits gesehen, dass dies für Z[

    √−5] nicht der Fall ist.Satz 6.28: Für D = −2,−1, 2, 3 ist Z[ωD] Norm-euklidisch, d.h. die Funktionν : x 7→ |N(x)| ist Euklidisch. Damit sind diese Rings dann auch ZPE und Haupt-idealringe.

    Beweis. Sei nun x, y ∈ Z[ωD], y 6= 0 gegeben. In Q[√D] gibt es a, b ∈ Q mit

    x/y = a+ b√D

    Wir setzen nun c := bae = ba+1/2c und d := bbe. Dann gilt c ∈ Z und |a−c| ≤ 1/2.Wir definieren q := c + d

    √D ∈ Z[√D] ⊆ Z[ωD] und zeigen, dass für r := x − qy

    entweder r = 0 oder |N(r)| < |N(y)| gilt. Wir haben|N(r)| = |N(x− qy)| = |N(y(x

    y− q))| = |N(y) N(x

    y− q)|

    = |N(y) N((a+ b√D)− (c+ d

    √D))| = |N(y) N((a− c) + (b− d)

    √D)|

    = |N(y)| |((a− c)2 −D(b− d)2|Für die angegebenen D gilt nun |((a− c)2 −D(b− d)2| < 1 ¤

  • 42 6. QUADRATISCHE ZAHLKÖRPER

    Man kann den Beweis noch ein bischen optimieren und für ein paar weitere Debenfalls zeigen, dass Z[ωD] euklidisch ist.

    Im weiteren sei Z[ωD] immer Faktoriell!Satz 6.29: Es sei 1 6= D ∈ Z quadratfrei und p ∈ PZ eine Primzahl. Dann istentweder p irreduzibel in Z[ωD] oder es gibt ein irreduzibles Element π ∈ Z[ωD]mit p = ±ππ̄ = |Nπ|.

    Beweis. Sei p nicht irreduzibel in Z[ωD], dann gibt es x, y ∈ Z[ωD] mit p = xy, alsoauch N(p) = p2 = N(x) N(y). Da x und y keine Einheiten sind, so folgt N(x) = ±pund x ist irreduzibel. ¤Definition 6.30: Sei 1 6= D qudratfrei und p ∈ PZ Prim. Dann heißt:(1) p träge in Z[ωD] falls p irreduzibel ist(2) p verzweigt, falls p = N(π) und π/π̄ ∈ Z[ωD](3) p zerlegt sonst.

    Für nicht faktorielle Ringe sind die Begriffe träge, verweigt und zerlegt über Ei-genschaften von Idealen definiert. Da dies hier jedoch zu viel Aufwand erfordert,behandeln wir nur ZPE, also Hauptidealringe.

    Beispiel 6.31: D = −2. Wir habe oben gesehen, dass Z[ω−2] = Z[√−2] euklidisch

    und ZPE ist. Es gilt

    (1) 5 ist Träge, denn es kann keien Elemente der Norm 5 geben.(2) 2 ist verzweigt: N(x) = ±2 genau dann, wenn x = ±

    √−2(3) 3 ist zerlegt, N(x) = ±3 impliziert x = ±1±

    √−2 und (1+√−2)/(1−√−2) =(1 +

    √−2)2/3 = (−1 + 2√−2)/3 ist nicht ganz.

    Ziel ist der folgende Satz (der so ähnlich auch im Allgemeinen gültig ist, jedochetwas anders bewiesen werden muss).

    Satz 6.32: Sei 1 6= D quadratfrei so, dass Z[ωD] ZPE ist. Ferner sei 2 6= p ∈ PZeine Primzahl. Dann gilt

    (1) p ist genau dann verzweigt, wenn(

    Dp

    )= 0 gilt

    (2) p ist zerlegt, genau dann, wenn(

    Dp

    )= 1

    (3) p ist träge für(

    Dp

    )= −1.

    Lemma 6.33: Sei D, p wie oben und zusätzlich π ∈ Z[ωD prim mit p = ±N(π).Dann ist p genau dann verzweigt, wenn p|D gilt.

    Beweis. Seien a, b ∈ Z mit π =a+ b

    √D D ≡ 2, 4 mod 4

    a/2 + b/2√D D ≡ 1 mod 4 .

    Gelte nun p|D, also D = pc = ±ππ̄c, also π|D = √D√D/ π prim, also π|√D.Wegen

    π − π̄ =

    2b√D D ≡ 2, 3 mod 4

    b√D D ≡ 1 mod 4

    Ist π ein Teiler von π̄. Wenn wir jetzt noch mal .̄ anwenden, so erhalten wir π̄|π undπ und π̄ sind assoziiert wie gefordert.

  • 6. QUADRATISCHE ZAHLKÖRPER 43

    Sei nun p verzweigt. Es gilt

    a2 −Db2 =

    N(π) = ±p D ≡ 2, 3 mod 44 N(π) = ±4p D ≡ 1 mod 4

    Also p|a2 −Db2. Falls nun p|b gelten würde, so folgt p|a und p2|p was verboten ist.Nach Voraussetzung gilt

    Z[ωD] 3 ππ̄

    =π2

    p=

    a2+Db2

    p+ 2ab

    p

    √D

    22+Db2

    2p+ 2ab

    4p

    √D D ≡ 1 mod 4

    Damit folgt sofort p|2ab, also p|a. Damit eralten wirp|a2 − N(π) = a2 − (a2 −Db2) = Db2

    und somit p|D. ¤Lemma 6.34: p, D wie Oben. Falls es ein x ∈ Z gibt mit p|x2 −D, so ist p nichtträge.

    Beweis. Angenommen, p ist träge, so ist p irreduzibel in Z[ωD] also prim da wir inZPE (also Ha


Recommended