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

Neue Frage »

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 Big Laugh (Zahlen der Form mit ungerade). Außerdem brauche ich viele Erkenntnisse des Jacobisymbols bzw. des Legendresymbols.
Nun bin ich für eine beliebige Proth'schen Zahl auf der Suche nach einer ganzen Zahl so, dass das Jacobisymbol ist. Die Frage ist, wie weit muss ich dabei höchstens gehen.
Ich konnte bereits zeigen, dass für Proth'sche Zahlen gilt: Außerdem gilt . Von daher reicht es, wenn ich mir die ganzen Zahlen zwischen und anschaue.

Was habe ich bisher!?
Wenn zusammengesetzt ist, dann gibt es einen Primteiler . Für das Jacobisymbol erhalte ich dann .
Hier muss ich also höchstens bis zur Wurzel laufen.

Aber was, wenn prim ist.
Dann fällt das Jacobisymbol mit dem Legendresymbol zusammen. Das bedeutet:
ist quadratischer Rest mod
(Und da ich nur die Zahlen bis prüfe, werde ich auch kein Vielfaches von erwischen und daher nicht das Ergebnis bekommen).

Wann bekomme ich also spätestens eine ?
Hier war meine Idee dass ich ja weiß, dass es quadratische Reste und auch Nichtreste gibt. Allerdings sind die zufällig verteilt. Es könnte also sein, dass ich wirklich bis laufen muss.
Aber ich konnte kein Beispiel finden, wo wirklich die Zahlen jeweils eine 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 sagt die Grafik also das Verhältnis :[attach]57310[/attach]
HAL 9000 Auf diesen Beitrag antworten »

Für prime ist das kleinste mit auf jeden Fall eine Primzahl:

Denn ist zusammengesetzt mit , dann folgt aus ja oder , Widerspruch dazu, dass die kleinste solche Zahl ist.

Mehr fällt mir jetzt allerdings auch nicht ein bei der Suche nach einem solchen .
Malcang Auf diesen Beitrag antworten »

HAL 9000, ich bedanke mich vielmals geschockt Freude
Das war in der Tat eine Frage, die mich beschäftigt.
Nun weiß ich, dass ich mich in beiden Fällen ( prim oder nicht) ausschließlich auf die Primzahlen stürzen muss.

Für den Fall zusammengesetzt weiß ich, dass ich höchstens bis 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!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »