Quadratische Reste von Primzahlen, Gleichungssystem

Neue Frage »

SoulOfMidgard Auf diesen Beitrag antworten »
Quadratische Reste von Primzahlen, Gleichungssystem
Meine Aufgabe ist es die kleinste Primzahl q zu finden, sodass 2,3, 5 quadratische Reste Modulo q sind und 7 quadratischer Nichtrest. Dies gibt mir ein Gleichungssystem:






Mithilfe der Tatsache dass ich (p-1)/2 quadratische Reste hatte wollte ich darauf schliessen, dass meine Zahl mindestens 7 oder größer sein muss. Aber brute force brachte mich hier nicht weiter.

Meine nächste Idee war die Eulersche phi-Funktion zu nutzen, da diese mir zumindest


...

ausgibt. Aber auch dies trug bis jetzt keine Früchte. Hat jemand anderweitig eine Idee?
Huggy Auf diesen Beitrag antworten »
RE: Quadratische Reste von Primzahlen, Gleichungssystem
Zitat:
Original von SoulOfMidgard
Aber brute force brachte mich hier nicht weiter.

Mein Rechner kommt auf .
 
 
HAL 9000 Auf diesen Beitrag antworten »

Man kann sich der Sache natürlich auch mit dem Quadratischen Reziprozitätsgesetz nähern. Der Aufwand ist aber eher gerechtfertigt, wenn man alle (!) Primzahlen mit diesen Eigenschaften charakterisieren will. So führen z.B. alleine die ersten beiden Bedingungen "2 und 3 quadratische Reste modulo " zu .
SoulOfMidgard Auf diesen Beitrag antworten »
RE: Quadratische Reste von Primzahlen, Gleichungssystem
Zitat:
Original von Huggy
Zitat:
Original von SoulOfMidgard
Aber brute force brachte mich hier nicht weiter.

Mein Rechner kommt auf .


Ja aber ich müsste natürlich auch zeigen, dass es die kleinste Zahl ist und ich wüsste nicht wie ich das anstellen sollte ohne zu zeigen dass jede kleinere nicht funktioniert und per Hand wäre das deutlich zu viel Arbeit (ich muss es händisch lösen)..
SoulOfMidgard Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Man kann sich der Sache natürlich auch mit dem Quadratischen Reziprozitätsgesetz nähern. Der Aufwand ist aber eher gerechtfertigt, wenn man alle (!) Primzahlen mit diesen Eigenschaften charakterisieren will. So führen z.B. alleine die ersten beiden Bedingungen "2 und 3 quadratische Reste modulo " zu .


Ich sehe gerade nicht wie ich das anwenden muss. Benutze ich dieses nicht um ein Legendre Symbol zu berechnen? Wie soll ich es hier nutzen um ein System von Gleichungen die das Legendre Symbol beinhalten zu lösen?
HAL 9000 Auf diesen Beitrag antworten »

Aus dem Quadratischen Reziprozitätsgesetz inklusive Ergänzungssätzen folgt







.

(1) bedeutet oder , letzteres verfehlt aber "Filter" (2), bleibt also erstmal nur übrig. Jetzt kann man das mit (3) und (4) weiter eingrenzen...
SoulOfMidgard Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
(1) bedeutet oder .

Es will sich mir nicht recht erschließen, wie sie darauf kommen. Ich nehme an das soll daraus resultieren, dass der Exponent ungerade sein muss, also aber damit komme ich nach Umformung auf . Was mache ich falsch? Desweiteren sehe ich indes auch nicht wie ich an diese "k-Bedingungen" für die anderen Gleichungen komme..
HAL 9000 Auf diesen Beitrag antworten »

1) Für gilt , d.h. es wird nur dann 1, wenn gerade ist. Also müssen die Primzahlen die Form haben.


2) Jetzt schauen wir uns Gleichung (2) an unter Berücksichtigung von sowie :

erfordert .

erfordert ebenfalls .

Damit bleibt jeweils nur und damit übrig.


3) Nun Gleichung (3), dabei berücksichtigen wir sowie :

erfordert .

erfordert .

Insgesamt bedeutet dies oder


4) Schließlich und endlich Gleichung (4), dabei berücksichtigen wir sowie :

erfordert .

erfordert .

erfordert .

erfordert .

Das ergibt die möglichen Primzahlkandidaten . Von denen ist dann 71 die kleinste mögliche Primzahl, ja.


Wie gesagt, ein enormer Aufwand, und man hat viel mehr erreicht, als man eigentlich braucht: Nämlich eine genaue Charakterisierung der Primzahlen, die diesen vier Bedingungen genügen.
Neue Frage »
Antworten »



Verwandte Themen

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