Arithmetische Progression

11.09.2010, 16:22

saz

Arithmetische Progression

Folgendes: Sei $\begin{eqnarray*} a \in \mathbb{P} \end{eqnarray*}$ (Primzahl) und seien $\begin{eqnarray*} a,a+d, \ldots, a + h \cdot d \end{eqnarray*}$ Primzahlen mit $\begin{eqnarray*} n \in \mathbb{N} \end{eqnarray*}$ . Dann teilt jede Primzahl p<h die Zahl d.

Sicher nicht schwer zu beweisen, aber ich seh es gerade überhaupt nicht. (Auch wenn ich nicht dran zweifele, dass es stimmt.) unglücklich

Edit: Noch einen Einfall gehabt. Wenn p prim ist, dann ist $\begin{eqnarray*} \mathbb{Z}_p \end{eqnarray*}$ ein Körper und jedes Element 0<e<p eine Einheit (besitzt also multiplikatives Inverses). Oben folgt also, dass $\begin{eqnarray*} d \mod p \end{eqnarray*}$ ein multipliaktives Inverses besitzt, damit

$\begin{eqnarray*} (a+h \cdot d) \mod p = 0<br /> \Leftrightarrow (h \cdot d) \mod p = - (a \mod p)<br /> \Leftrightarrow (h \cdot (d \mod p)) \mod p = - (a \mod p) \end{eqnarray*}$

und für $\begin{eqnarray*} h := ( - (a \mod p) \cdot (d \mod p)^{-1} ) \mod p \end{eqnarray*}$ erhält man das gewünschte h ... oder?

11.09.2010, 18:48

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von saz
Folgendes: Sei $\begin{eqnarray*} a \in \mathbb{P} \end{eqnarray*}$ (Primzahl) und seien $\begin{eqnarray*} a,a+d, \ldots, a + h \cdot d \end{eqnarray*}$ Primzahlen mit $\begin{eqnarray*} n \in \mathbb{N} \end{eqnarray*}$ . Dann teilt jede Primzahl p<h die Zahl d.

Soweit ich erkenne, gilt das sogar für alle Primzahlen $\begin{eqnarray*} p \end{eqnarray*}$ mit $\begin{eqnarray*} p\leq h \end{eqnarray*}$ (also $\begin{eqnarray*} h \end{eqnarray*}$ mit eingeschlossen).

Deine Idee geht schon in die richtige Richtung, allerdings kannst du $\begin{eqnarray*} h \end{eqnarray*}$ nicht einfach definieren, $\begin{eqnarray*} h \end{eqnarray*}$ ist ja vorgegeben!

Was du meinst ist, dass es im Fall $\begin{eqnarray*} p \nmid d \end{eqnarray*}$ ein $\begin{eqnarray*} k \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq k\leq p-1 \end{eqnarray*}$ (und damit insbesondere auch $\begin{eqnarray*} k<h \end{eqnarray*}$ ) mit $\begin{eqnarray*} (a+k\cdot d) \bmod p = 0 \end{eqnarray*}$ gibt. Das allein reicht allerdings noch nicht zum Widerspruch, denn es könnte ja gerade $\begin{eqnarray*} a+kd=p \end{eqnarray*}$ gelten... Augenzwinkern

11.09.2010, 23:24

saz

Auf diesen Beitrag antworten »

Hm ja, das stimmt natürlich, hatte dem h dort zwei Bedeutungen zugewiesen. Ich meinte aber das, was du geschrieben hast. Mit deinem Einwand hast du aber recht, da muss ich nochmal überlegen.

13.09.2010, 09:02

René Gruber

Auf diesen Beitrag antworten »

Eine Lösung für das von mir angesprochene Problem der Vermeidung von $\begin{eqnarray*} a+kd=p \end{eqnarray*}$ besteht in folgendem, sehr oft in ähnlicher Weise erfolgreichen Trick. Zunächst mal formt man die (von mir oben verschärfte) Behauptung

Zitat:

Seien $\begin{eqnarray*} a,d,h \in \mathbb{N} \end{eqnarray*}$ so gegeben, dass $\begin{eqnarray*} a+jd\in\mathbb{P} \end{eqnarray*}$ für $\begin{eqnarray*} j=0,1,\ldots,h \end{eqnarray*}$ gilt.
Man zeige: Jede Primzahl $\begin{eqnarray*} p\leq h \end{eqnarray*}$ teilt die Zahl $\begin{eqnarray*} d \end{eqnarray*}$ .

äquivalent um:

Zitat:

Man zeige: Die kleinste Primzahl $\begin{eqnarray*} q \end{eqnarray*}$ , die nicht die Zahl $\begin{eqnarray*} d \end{eqnarray*}$ teilt, ist größer als $\begin{eqnarray*} h \end{eqnarray*}$ .

Beweis (zumindest der Anfang): Für $\begin{eqnarray*} h\leq 1 \end{eqnarray*}$ oder $\begin{eqnarray*} d=0 \end{eqnarray*}$ ist nichts zu beweisen, es sei also im folgenden stets $\begin{eqnarray*} h\geq 2 \end{eqnarray*}$ und $\begin{eqnarray*} d\geq 1 \end{eqnarray*}$ .

Angenommen, es ist $\begin{eqnarray*} a<q \end{eqnarray*}$ . Da $\begin{eqnarray*} a \end{eqnarray*}$ ja außerdem Primzahl ist, muss dann $\begin{eqnarray*} a \mid d \end{eqnarray*}$ gelten und folglich auch $\begin{eqnarray*} a \mid (a+d) \end{eqnarray*}$ , letzteres im Widerspruch zu $\begin{eqnarray*} (a+d)\in\mathbb{P} \end{eqnarray*}$ . Demnach war die Annahme falsch, und es ist $\begin{eqnarray*} a\geq q \end{eqnarray*}$ .

Weiter im Text dann wie bei dir, d.h. man nutzt, dass unter den Zahlen $\begin{eqnarray*} a+jd \end{eqnarray*}$ für $\begin{eqnarray*} j=1,\ldots,q \end{eqnarray*}$ genau eine durch $\begin{eqnarray*} q \end{eqnarray*}$ teilbare Zahl $\begin{eqnarray*} a+kd \end{eqnarray*}$ existiert, die diesmal (!) echt größer als $\begin{eqnarray*} q \end{eqnarray*}$ ist, was im Fall $\begin{eqnarray*} q\leq h \end{eqnarray*}$ einen Widerspruch zur Voraussetzung $\begin{eqnarray*} a+kd\in\mathbb{P} \end{eqnarray*}$ darstellt.

13.09.2010, 09:46

saz

Auf diesen Beitrag antworten »

Das ist ja toll - über eine Fallunterscheidung hatte ich auch schon nachgedacht, aber eben eine über d und nicht über a. Danke! smile

Neue Frage »

Antworten »

Arithmetische Progression

Verwandte Themen