Quadratische (Nicht)reste; Jacobisymbol ergibt 0 oder -1

17.10.2023, 14:04	Malcang	Auf diesen Beitrag antworten »
Quadratische (Nicht)reste; Jacobisymbol ergibt 0 oder -1 Hallo zusammen, ich bin ja immer noch an den Proth'schen Zahlen dran (Zahlen der Form $\begin{eqnarray} n = h\cdot 2^k + 1 \end{eqnarray}$ mit $\begin{eqnarray} h<2^k \end{eqnarray}$ ungerade). Außerdem brauche ich viele Erkenntnisse des Jacobisymbols bzw. des Legendresymbols. Nun bin ich für eine beliebige Proth'schen Zahl $\begin{eqnarray} n>3 \end{eqnarray}$ auf der Suche nach einer ganzen Zahl $\begin{eqnarray} D \end{eqnarray}$ so, dass das Jacobisymbol $\begin{eqnarray} \left( \frac{D}{n}\right) \neq 1 \end{eqnarray}$ ist. Die Frage ist, wie weit muss ich dabei höchstens gehen. Ich konnte bereits zeigen, dass für Proth'sche Zahlen $\begin{eqnarray} n>3 \end{eqnarray}$ gilt: $\begin{eqnarray} \left( \frac{-1}{n}\right) = 1. \end{eqnarray}$ Außerdem gilt $\begin{eqnarray} \left( \frac{D}{n}\right) = \left( \frac{D\mod n}{n}\right) \end{eqnarray}$ . Von daher reicht es, wenn ich mir die ganzen Zahlen zwischen $\begin{eqnarray} 0 \end{eqnarray}$ und $\begin{eqnarray} n-1 \end{eqnarray}$ anschaue. Was habe ich bisher!? Wenn $\begin{eqnarray} n \end{eqnarray}$ zusammengesetzt ist, dann gibt es einen Primteiler $\begin{eqnarray} p\leq \sqrt{n} \end{eqnarray}$ . Für das Jacobisymbol erhalte ich dann $\begin{eqnarray} \left( \frac{p}{n}\right) = 0 \end{eqnarray}$ . Hier muss ich also höchstens bis zur Wurzel laufen. Aber was, wenn $\begin{eqnarray} n \end{eqnarray}$ prim ist. Dann fällt das Jacobisymbol $\begin{eqnarray} \left( \frac{D}{n}\right) \end{eqnarray}$ mit dem Legendresymbol zusammen. Das bedeutet: $\begin{eqnarray} \left( \frac{D}{n}\right) = 1 \Leftrightarrow D \end{eqnarray}$ ist quadratischer Rest mod $\begin{eqnarray} n. \end{eqnarray}$ (Und da ich nur die Zahlen $\begin{eqnarray} 0 \end{eqnarray}$ bis $\begin{eqnarray} n \end{eqnarray}$ prüfe, werde ich auch kein Vielfaches von $\begin{eqnarray} n \end{eqnarray}$ erwischen und daher nicht das Ergebnis $\begin{eqnarray} 0 \end{eqnarray}$ bekommen). Wann bekomme ich also spätestens eine $\begin{eqnarray} -1 \end{eqnarray}$ ? Hier war meine Idee dass ich ja weiß, dass es $\begin{eqnarray} \frac{n-1}{2} \end{eqnarray}$ quadratische Reste und auch Nichtreste gibt. Allerdings sind die zufällig verteilt. Es könnte also sein, dass ich wirklich bis $\begin{eqnarray} \frac{n+1}{2} \end{eqnarray}$ laufen muss. Aber ich konnte kein Beispiel finden, wo wirklich die Zahlen $\begin{eqnarray} 1,2,\dots,\frac{n-1}{2} \end{eqnarray}$ jeweils eine $\begin{eqnarray} 1 \end{eqnarray}$ ergeben. Habt ihr dafür ein Beispiel? Oder wie könnte ich vielleicht sinniger daran gehen? Edit: Ich hab mal für die ersten 1.000 Primzahlen untersucht, wann das erste Mal ein quadratischer Nichtrest auftritt. Für festes $\begin{eqnarray} n \end{eqnarray}$ sagt die Grafik also das Verhältnis $\begin{eqnarray} \frac{\text{erstes Auftreten der -1}}{n-1} \end{eqnarray}$ :[attach]57310[/attach]
17.10.2023, 17:43	HAL 9000	Auf diesen Beitrag antworten »
Für prime $\begin{eqnarray} n\geq 3 \end{eqnarray}$ ist das kleinste $\begin{eqnarray} D>0 \end{eqnarray}$ mit $\begin{eqnarray} \left( \frac{D}{n} \right) = -1 \end{eqnarray}$ auf jeden Fall eine Primzahl: Denn ist $\begin{eqnarray} D=ab \end{eqnarray}$ zusammengesetzt mit $\begin{eqnarray} 1<a<D,1<b<D \end{eqnarray}$ , dann folgt aus $\begin{eqnarray} \left( \frac{D}{n} \right) = -1 \end{eqnarray}$ ja $\begin{eqnarray} \left( \frac{a}{n} \right) = -1 \end{eqnarray}$ oder $\begin{eqnarray} \left( \frac{b}{n} \right) = -1 \end{eqnarray}$ , Widerspruch dazu, dass $\begin{eqnarray} D \end{eqnarray}$ die kleinste solche Zahl ist. Mehr fällt mir jetzt allerdings auch nicht ein bei der Suche nach einem solchen $\begin{eqnarray} D \end{eqnarray}$ .
17.10.2023, 19:07	Malcang	Auf diesen Beitrag antworten »
HAL 9000, ich bedanke mich vielmals Das war in der Tat eine Frage, die mich beschäftigt. Nun weiß ich, dass ich mich in beiden Fällen ( $\begin{eqnarray} n \end{eqnarray}$ prim oder nicht) ausschließlich auf die Primzahlen stürzen muss. Für den Fall $\begin{eqnarray} n \end{eqnarray}$ zusammengesetzt weiß ich, dass ich höchstens bis $\begin{eqnarray} \sqrt{n} \end{eqnarray}$ laufen muss. Im Falle der Primalität scheint es da nicht so einfach zu sein, ich konnte da nur heuristische Ergebnisse finden. Aber das ist ja auch schonmal was. Vielen Dank nochmal!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »