Anzahl Primzahlen, quadratische Reste |
26.10.2014, 19:15 | mathemensch123 | Auf diesen Beitrag antworten » | ||
Anzahl Primzahlen, quadratische Reste 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? |
||||
26.10.2014, 19:50 | tmo | Auf diesen Beitrag antworten » | ||
Die Werte von hängen ja bekanntlich (?) nur von der Restklasse ab. |
||||
26.10.2014, 20:54 | 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? |
||||
26.10.2014, 20:59 | 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. |
||||
26.10.2014, 21:22 | 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? |
||||
26.10.2014, 21:31 | tmo | Auf diesen Beitrag antworten » | ||
Die gesuchte Anzahl wird damit zu , wobei die Summe über diejenigen a mit läuft. |
||||
Anzeige | ||||
|
||||
26.10.2014, 21:38 | 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... |
||||
26.10.2014, 21:50 | tmo | Auf diesen Beitrag antworten » | ||
Wenig Überraschend: Die Hälfte von 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. |
||||
26.10.2014, 21:53 | mathemensch123 | Auf diesen Beitrag antworten » | ||
Danke, danke, natürlich! Also kommt letztenendes als Gesamtanzahl, die gesucht war, einfach ? |
||||
26.10.2014, 22:22 | tmo | Auf diesen Beitrag antworten » | ||
Ja zumindest asymptotisch, wenn B im Vergleich zu n genügend groß ist. |
||||
26.10.2014, 22:51 | 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? |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|