Anzahl Primzahlen, quadratische Reste

Neue Frage »

mathemensch123 Auf diesen Beitrag antworten »
Anzahl Primzahlen, quadratische Reste
Meine Frage:
Sei n ein Produkt von zwei Primzahlen und B irgendeine natürliche Zahl.

Gesucht ist die Anzahl von Primzahlen kleiner oder gleich B mit (Legendre-Symbol), also für die n ein quadratischer Rest modulo p ist.

Als Hilfestellung habe ich den Dirichletschen Satz gegeben, dass für a,m teilerfremd.

Meine Ideen:
Ich weiß ehrlich gesagt nicht, wie der Satz mir helfen soll. Allerdings weiß ich auch nicht, wie ich da sonst ran kann. n=ab ist ein quadratischer Rest mod p genau dann, wenn sowohl a als auch b welche sind oder wenn weder a noch b welche sind.

Hat jemand vielleicht eine Hilfestellung?
tmo Auf diesen Beitrag antworten »

Die Werte von hängen ja bekanntlich (?) nur von der Restklasse ab.
mathemensch123 Auf diesen Beitrag antworten »

Das ist mir leider nicht bekannt...Mir ist das quadratische Reziprozitätsgesetz bekannt (einschl. Ergänzungssätzen), aber nicht diese Verallgemeinerung.

Gibt's da einen einfachen Weg, draufzustoßen?
tmo Auf diesen Beitrag antworten »

Ja, den gibt es



Das erste Vorzeichen hängt von n und p+4n modulo 4 ab.
Das zweite Vorzeichen hängt von n und p modulo 4 ab. Da gibt es aber keinen Unterschied. Also ist die Gleichung richtig.
mathemensch123 Auf diesen Beitrag antworten »

Stimmt, wirklich nicht schwer. Aber nun habe ich das, aber was sagt mir das für die Aufgabe?

Gesucht ist und dies ist jetzt , aber wie kann ich dann den Satz von Dirichlet anwenden?
tmo Auf diesen Beitrag antworten »

Die gesuchte Anzahl wird damit zu

, wobei die Summe über diejenigen a mit läuft.
 
 
mathemensch123 Auf diesen Beitrag antworten »

aaah ja natürlich - die Gesamtanzahl lässt sich in die Fälle aufteilen, in denen man je eine Restklasse mod 4n betrachtet, daher die Bedingung ggt(a,4n)=1?

Welche Bedingung muss ich an die a stellen? Meinst du ? Müsste ja, oder?

Dann wäre natürlich der nächste Schritt: Wie viele a's mit dieser Eigenschaft gibt es? Da kommt man ja wieder auf dieselbe Frage...
tmo Auf diesen Beitrag antworten »

Zitat:
Original von mathemensch123
Dann wäre natürlich der nächste Schritt: Wie viele a's mit dieser Eigenschaft gibt es?


Wenig Überraschend: Die Hälfte von Augenzwinkern


Letztendlich haben wir das Problem in folgendem Maße vereinfacht: Statt die Anzahl der Primzahlen, bzgl. dessen das Legendre-Symbol 1 ist, bis zur Grenze B (die bel. groß sein kann) zu suchen, müssen wir jetzt nur noch die Anzahl der Restklassen finden, bzgl. dessen das Jacobi-Symbol 1 ist. Das ist ein einfacheres Problem.
mathemensch123 Auf diesen Beitrag antworten »

Danke, danke, natürlich!

Also kommt letztenendes als Gesamtanzahl, die gesucht war, einfach ?
tmo Auf diesen Beitrag antworten »

Ja zumindest asymptotisch, wenn B im Vergleich zu n genügend groß ist.
mathemensch123 Auf diesen Beitrag antworten »

Moment, ich wollte das gerade nochmal durchgehen und hänge jetzt doch noch kurz: Warum ist es einfacher, die Anzahl der Restklassen zu finden, bzgl. dessen Jacobi-Symbol 1 ist?

Also warum gibt es genau davon?

Klar ist: Wir haben für jede Restklasse entweder +1 oder -1, aber warum wissen wir, dass diese sich abwechseln? Und warum wissen wir das nicht schon direkt für die Primzahlen?
Neue Frage »
Antworten »



Verwandte Themen

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