Euklidische Beweise für Primzahlen in einigen arithmetischen

Euklidische Beweise für Primzahlen in
einigen arithmetischen Progressionen
Bis zum jetzigen Zeitpunkt sind für die Aussage, dass in jeder arithmetischen Progression l mod k mit ggT(l, k) = 1 unendlich viele Primzahlen
enthalten sind, nur Beweise bekannt, die analytische Methoden verwenden.
Ein Ziel ist es, dass man die komplette Aussage beweist ohne gröÿere analytische Hilfsmittel zu benutzen. Wir werden hier zumindest für einige arithmetische Progressionen einen Beweis liefern können, der auf solche Hilfsmittel
verzichtet.
Die Idee hinter einem euklidischen Beweis ist es, dass man sich ein Polynom konstruiert,
welches einem hilft eine neue Primzahl ≡ l mod k zu nden unter der zuvor getroenen
Annahme, dass es nur endlich viele Primzahlen in dieser Progression gäbe. Beispielsweise
erfüllt das Polynom x + 1 das Gewünschte, wenn man das klasssische Ergebnis beweisen
möchte, dass es unendlich viele Primzahlen gibt. Hierbei wurde k = 1 gewählt.
Wir werden später nochmals kurz darauf eingehen, was man sich genau unter einem
euklidischen Beweis vorzustellen hat.
Satz (Schur(1912), Murty(2006))
Ein euklidischer Beweis existiert genau dann für die arithmetische Progression l mod k,
wenn l2 ≡ 1 mod k gilt.
Denition
Für f ∈ Z[x] ist p ∈ P ein Primteiler von f , falls ein n ∈ Z mit p | f (n) existiert, in
Zeichen p | f . Die Menge aller Primteiler von f bezeichnen wir mit P(f ).
Zunächst besprechen wir ein paar Eigenschaften von Polynomen bezüglich ihrer Primteiler. Der Beweis zur ersten Eigenschaft steht ganz im Zeichen von Euklids Beweis.
Satz 1
Für f ∈ Z[x], nicht-konstant, gilt |P(f )| = ∞.
1
Wir dürfen f (0) = c 6= 0 annehmen, da die Behauptung sonst klar ist (da sonst
für alle f ∈ Z[x] automatisch p | f (p) gilt). Da f (x) = ±1 nur endlich viele Lösungen hat
folgt, dass f wenigstens einen Primteiler besitzen muss. Wir nehmen nun an, dass f nur
endlich viele Primteiler p1 , . . . , pn besitzt. Sei Q = p1 p2 . . . pn . Es gilt f (Qcx) = cg(x)
für ein Polynom g ∈ Z[x] mit g = 1 + b1 x + b2 x2 + . . . und Q | bi für alle i ≤ deg(g).
Nach obigem Argument hat auch g wenigstens einen Primteiler p. Es gilt oensichtlich
p | g ⇒ p | f . Hierbei muss aber p - Q gelten, sonst gölte auch p | 1. Somit muss p aber
ein weiterer Primteiler von f sein. Ein Widerspruch. Also hat F tatsächlich unendlich
viele Primteiler.
Beweis.
Das nachfolgende Ergebnis wurde zuerst vom norwegischen Mathematiker T. Nagell
bewiesen. Es wird hier ein Körpertheoretischer Beweis gegeben. Nagell selbst hatte einen
sehr viel elementareren Beweis geliefert (Siehe hierzu [?])
Satz 2
Für f, g ∈ Z[x], beide nicht-konstant, gilt |P(f ) ∩ P(g)| = ∞.
Sei α eine Nullstelle von f und β eine Nullstelle von g. Nach einem Satz von
Dedekind ist, bis auf endlich viele Ausnahmen, p ∈ P genau dann ein Primteiler von f ,
wenn p einen Primidealfaktor von Restklassengrad 1 in Q(α) besitzt. (Siehe hierzu z.B.
[?, S. 65]) Die gleiche Aussage trit entsprechend auch auf g zu.
Betrachte nun den Körper Q(α, β) = Q(γ) für ein γ ∈ Q(α, β). Falls h nun das
Minimalpolynom von γ ist, folgt mit Satz 1 und wiederum mit dem Satz von Dedekind
folgt, dass es unendlich viele Primzahlen, die einen Primidealfaktor mit Restklassengrad
1 in Q(α, β) besitzen, gibt. Diese Primzahlen haben somit auch einen Primidealfaktor
mit Restklassengrad 1 in Q(α) sowie Q(β). Es folgt, dass, mit einer endlichen Anzahl
von Ausnahmen, all diese Primzahlen in P(f ) und zugleich in P(g) liegen.
Beweis.
Ein weiteres klassisches Ergebnis ist, dass alle Primteiler, mit Ausnahme von endlichen
vielen, des k-ten Kreisteilungspolynoms φk erfüllen, dass sie ≡ 1 mod k sind. Auf dieses
Ergebnis wird später nochmals kurz eingegangen. Mit Satz 2 folgt somit, dass jedes
nicht-konstante Polynom in Z[x] unendlich viele Primteiler ≡ 1 mod k, für jedes k ∈ N,
besitzt.
Deswegen ist die endgültige Idee hinter einem euklidischen Beweis für die Progression l mod k, dass es ein Polynom in Z[x] gibt, wessen Primteiler, mit endlich vielen
Ausnahmen, allesamt ≡ 1, l mod k sind.
Satz 3
Sei H eine Untergruppe von (Z/kZ)∗ . Dann existiert ein irreduzibles Polynom f , so
dass alle Primteiler von f , bis auf endlich viele Ausnahmen, zu den Restklassen von H
gehören.
Wir verwenden (Z/kZ)∗ ∼
= Gal(Q(ζ)/Q) wobei ζ eine primitive k -te Einheitswurzel ist.
Beweis.
2
Sei also Q(η) der Fixkörper von H , wobei η = h(ζ) für ein h ∈ Z[x]. Seien m1 , . . . , ms
Nebenklassenrepräsentanten von H in (Z/kZ)∗ .
Setze ηi = h(ζ mi ) für i = 1, . . . , s. Angenommen diese wären nicht paarweise verschieden. Sei σi der Automorphismus von Q(ζ)/Q, der ζ auf ζ i abbildet. Dann ist gibt es
i 6= j mit σmi (η) = σmj (η). Dies hat somit σmi m−1 (η) = η zur Folge, womit σmi m−1 also
j
j
Q(η) xiert und somit mi und mj in der gleichen Nebenklasse von H liegen müssten, ein
Widerspruch. Somit sind die ηi die paarweise verschiedenen Konjugierten von η.
Deniere nun
s
Y
f (x) :=
(x − ηi ).
i=1
Nach dem soeben gezeigten ist f (x) ein irreduzibles Polynom in Z[x]. Wir zeigen, dass
dieses f die Bedingungen im Satz erfüllt. Sei p ein Primteiler von f , mit p - k und
p - D(f ) (D(f ) ist hierbei die Diskriminante von f ). Beachte: wir schlossen nur endlich
viel Primzahlen hierbei aus.
Da nun p ein Primteiler von f ist, existiert ein a ∈ Z so, dass
s
Y
f (a) =
(a − ηi ) ≡ 0 mod p
i=1
gilt.
Sei nun p ein Primideal, das (p) teilt. Für dieses muss p | (a − ηi ) für ein i ∈ {1, . . . , s}
gelten. Es gilt nun ap ≡ a mod p und somit auch ap ≡ a mod p. Aus dem gleichen Grund
folgt auch h(x)p ≡ h(xp ) mod p. Wir erhalten damit folgende Kongruenzen:
h(ζ mi ) = ηi ≡ a ≡ ap ≡ ηip = h(ζ mi )p ≡ h(ζ pmi ) mod p.
Insbesondere gilt also p | (h(ζ mi ) − h(ζ pmi )). Weiter ist, da p - k, auch ggT(pmi , k) = 1,
womit h(ζ pmi ) = ηj , für ein j ∈ {1, . . . , s}, folgt.
Wir nehmen nun an, dass h(ζ pmi ) 6= h(ζ mi ) gilt. Dann gölte p | D(f ) und da D(f ) ∈ Z
folgte auch p | D(f ) (Beachte hierbei, dass dann ηj − ηi = h(ζ pmi ) − h(ζ mi ) als Faktor
in D(f ) vorkäme). Dies wiederspricht unserer Wahl von p. Also gilt h(ζ pmi ) = h(ζ mi )
und somit wir ηi von dem Automorphismus σp xiert. Es gilt also auch, dass Q(ηi ) von
σp xiert wird. Es ist klar, dass auch Q(ηi ) eine Galoiserweiterung ist, womit schlieÿlich
Q(ηi ) = Q(η) folgt. Also xiert σp somit Q(η) und p gehört zu einer der Restklassen von
H.
Satz 4
Sei f wie in Satz 3 konstruiert. Dann sind alle Primzahlen, die zu den Restklassen von
H gehören, Primteiler von f .
Beweis.
Sei p eine Primzahl, die zu einer der Restklassen von H gehört. Also wird Q(η)
3
von σp xiert. Insbesondere also:
η p = h(ζ)p ≡ h(ζ p ) ≡ h(ζ) = η mod p.
Also gilt auch für jedes Primideal p, das p teilt, somit η p ≡ η mod p. Da OQ(η) ein
Dedekindring ist, ist OQ(η) /p ein Körper und xp − x hat maximal p Lösungen (Hierbei
bezeichnet OK den Ganzheitsring zu K ). Natürlich sind alle Elemente in Z/pZ Lösungen
zu diesem Polynom. Somit folgt η ≡ a mod p für ein a ∈ Z. Also p | f (a) und wiederum,
da f (a) ∈ Z, auch p | f (a), wie gewünscht.
Korollar
Sei φk das k-te Kreisteilungspolynom, dann gilt für alle Primteiler p von φk entweder
p ≡ 1 mod k oder p | k .
Beweis. Die Behauptung folgt folgt, wenn wir Satz 3 und 4 auf H = {1} anwenden. Wir
benutzen hierbei die Tatache, dass die einzigen Primzahlen, die D(φk ) teilen, die sind,
die auch k teilen. (Siehe hierzu z.B. [1, S. 52])
Satz 5
Wenn l2 ≡ 1 mod k gilt und es wenigstens eine Primzahl p ≡ l mod kgibt, dann existieren
unendlich viele Primzahlen dieser Art.
Der Fall l ≡ 1 mod k folgt direkt aus dem Korollar. Sei also l 6≡ 1 mod k.
Wir können also die Sätze 3 und 4 auf die Untergruppe H = {1, l} ≤ (Z/kZ)∗ anwenden. Sei L der Fixkörper von H . Wir denieren formal
Beweis.
h(x) := (u − x)(u − xl )
für ein u ∈ Z, welches wir noch später wählen. Falls m1 , . . . , ms Nebenklassenrepräsentanten von H in (Z/kZ)∗ sind, und wir u so wählen, dass alle h(ζ mi ) paarweise verschieden
sind, folgt L = Q(h(ζ)) (da die h(ζ mi ) alle möglichen verschiedenen Konjugierten von
h(ζ) sind). Beachte, dass wir hierbei nur endlich viele u ausgeschlossen haben (Es gibt
nur endlich viele Gleichungen h(ζ mi ) = h(ζ mj ) und diese haben alle nur endlich viele
Lösungen). Verwenden wir nun Satz 3 auf H mit η = h(ζ), erhalten wir ein Polynom
f ∈ Z[x] bei dem alle Primteiler, mit Ausnahme von endlich vielen, entweder ≡ 1 oder
≡ l mod k sind. Wir können dieses f explizit schreiben:
f (x)2 =
Y
(x − (u − ζ a )(u − ζ la ))
ggT(a,k)=1
(das Quadrat kommt daher, dass alle Nebenklassen aus zwei Elementen bestehen und
das Produkt über alle Elemente genommen wird). Man sieht, dass f (0) = φk (u) das k-te
Kreisteilungspolynom in u ist. Wir wählen nun u so, dass es ein echtes Vielfaches von k
ist, so dass f (0) = φk (u) ≡ 1 mod k erfüllt ist. (Alle Summanden von φk (u), auÿer dem
4
letzten, sind durch k teilbar und natürlich ist u so gewählt, dass es obige Einschränkungen
nicht verletzt.)
Wegen dem Korollar gilt, dass jeder Primteiler von φk entweder k teilt oder ≡ 1 mod k
ist. Also ist jeder Primteiler von φk (u) = f (0) somit ≡ 1 mod k.
Wähle nun eine Primzahl p ≡ l mod k mit p - D(f ) (wobei D(f ) die Diskriminante
von f ist). Wegen Satz 4 nden wir ein b mit p | f (b). Wir können b sogar so wählen, dass
p2 - f (b) gilt. Andernfalls gelte p2 | f (b) und somit f (b+p) ≡ f (b)+pf 0 (b) ≡ pf 0 (b) mod p2
(Für das erste Kongruenzzeichen siehe z.B. den Binomischen Lehrsatz). Aber da p - D(f )
hat f keine Nullstellen der Ordnung 2 bzgl.mod p womit f 0 (b) 6≡ 0 mod p(Doppelte
Nst.⇔ D(f ) = 0) Somit impliziert f (b) ≡ 0 mod p2 also f (b + p) 6≡ 0 mod p2 . Somit
könnten wir also auch b durch b + p ersetzen und haben p | f (b) und p2 - f (b) (durch
ebige Betrachtung sieht man auch f (b) ≡ 0 mod p ⇒ f (b + p) ≡ 0 mod p).
Wir nehmen nun an es gäbe nur endlich viele Primzahlen ≡ l mod k, seien diese
p = p1 , p2 , . . . , pr . Seien weiter q1 , . . . , qt alle Primteiler von D(f ).
Deniere Q := p2 p3 . . . pr q1 . . . qt . Nach dem Chinesischem Restsatz nden wir ein c mit.
c ≡ b mod p2
c ≡ 0 mod kQ
Also f (c) ≡ f (b) mod p2 und f (c) ≡ f (0) mod kQ. Wegen Satz 3 erfüllen alle Primteiler von f , dass sie k teilen oder D(f ) teilen oder ≡ 1, l modk sind.. Weil f (0) nur von
Primzahlen ≡ 1 mod k geteilt wird, folgt, dass f (c) nur von Primzahlen ≡ 1 mod k und
p ≡ l mod k geteilt wird. Da p2 - f (c), folgt also f (c) ≡ l mod k . Aber zugleich gilt auch
f (c) ≡ f (0) ≡ 1 mod k . Dies ist ein Widerspruch, da l 6≡ 1 mod k gewählt war. Dies
zeigt die Behauptung.
Wer sich für einen mehr elementar gehaltenen Beweis dieser Aussagen interessiert,
kann sich in [4] von Schur einlesen. Die Beweisideen aus diesem kleinen Skript stammen
alle aus [2]. In diesem Paper ndet sich der von Murty gegebene Beweis für die andere
Implikation. Auÿerdem bespricht er weitere Verallgemeinerungen der Hauptaussage.
Literatur
[1] Murty, M.R.; Esmonde, J.: Problems in Algebraic
Graduate Texts in Mathematics 190, (2005).
, Second Edition,
Number Theory
[2] Murty, M.R.: Prime Numbers In Certain Arithmetic Progressions, Functiones et Approximatio XXXV (2006), 249-259.
[3] Nagell, T.: Sur les diviseurs premiers des polynômes, Acta Arith, 15 (1969), 235-244.
[4] Schur, I.:
Über die Existenz unendlich vieler Primzahlen in einigen speziellen arith-
, S-B Berlin. Math. Ges., 11 (1912), 40-50.
metischen Progressionen
5