Jacobisymbol ergibt nur 0 oder 1 |
10.01.2023, 13:08 | Malcang | Auf diesen Beitrag antworten » | |||||||||
Jacobisymbol ergibt nur 0 oder 1 ich weiß über das Jacobisymbol ja folgendes: und . Es kann im Falle wenigstens eines Quadrates also nur 0 oder 1 herauskommen. Nun frage ich mich folgendes: Falls , ist dann eine Quadratzahl? Ich weiß gerade keinen Beweisansatz dafür. Edit: Ein Skript untersützt meine Vermutung. Alle Quadratzahlen n zwischen 1 und 10000 ergeben nur 0 oder 1 beim Jacobisymbol . Andererseits erhalte ich bei jeder ungeraden Nichtquadratzahl in dieser Range immer irgendwann den Wert -1. |
|||||||||||
10.01.2023, 13:55 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Eigentlich gar nicht so schwer: Wenn keine Quadratzahl ist, dann gibt es eine Primzahl , die in der Primfaktorzerlegung von ungeradzahlig oft auftaucht, d.h., mit ungeradem sowie einer nicht durch teilbaren Zahl . Dann gibt es ja sicher einen quadratischen Nichtrest von , während die lineare Kongruenz genau eine Lösung hat. Mit dieser Lösung setzen wir einfach und erhalten sowie zusammen also . |
|||||||||||
10.01.2023, 14:24 | Malcang | Auf diesen Beitrag antworten » | |||||||||
Hallo HAL 9000, vielen Dank für deine Zeit. Ich gehe deine Antwort gerade durch, durchgestiegen bin ich allerdings noch nicht. Der erste Absatz ist mir völlig klar. Dann schreibst du
Dies ist der Fall, da ich modulo genau so viele quadratische Reste wie Nichtreste finde.
Hier hänge ich gerade. Ich kann nichtmal genau sagen, warum. Ich verstehe den Gedankengang nicht, warum ich diese Kongruenz betrachten sollte |
|||||||||||
10.01.2023, 14:25 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Lies doch einfach weiter, dann sollte klar sein, warum man das braucht. Sinn und Zweck dieser Überlegungen ist es, ein mit zu konstruieren, was letztlich ja auch gelingt. Und genau das ist doch der fehlende Baustein in deinen Überlegungen im Eröffnungsbeitrag, dass so ein für Nichtquadratzahlen stets existiert - und das eben war der Beweis dazu. |
|||||||||||
10.01.2023, 14:38 | Malcang | Auf diesen Beitrag antworten » | |||||||||
Mein altbekanntes Problem Ich schaue mir das in Ruhe jetzt an und schreibe dazu einiges auf. Das kann manchmal dauern, daher nicht wundern wenn hier keine Rückmeldung kommt. Danke auf jeden Fall dafür! Könnte ich dieses Vorgehen dann nicht eigentlich in einen effizienten Test auf ungerade Quadratzahlen umsetzen? Im Speziellen möchte ich das natürlich für den Bosmatest nutzen. Dort ist der Nenner des Jacobisymbols ja ohnehin ungerade. Sollte also jeweils nur 0 oder 1 herauskommen, kann ich den Test ja dort sogar beenden mit dem Ergebnis "Zusammengesetzt" (da ungerade Quadratzahl). |
|||||||||||
10.01.2023, 14:44 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Ich hatte gemeint, das Jacobisymbol gibt es überhaupt nur für ungerade Nenner??? |
|||||||||||
Anzeige | |||||||||||
|
|||||||||||
10.01.2023, 14:48 | Malcang | Auf diesen Beitrag antworten » | |||||||||
Ja, richtig. Mir gehen wieder 5 Gedanken gleichzeitig durch den Kopf. Ich wollte auf die Effizienz als Test für ungerade Nichtquadratzahlen hinaus. Ich weiß nicht, wie man es sonst machen würde. Brute-Force natürlich mit
|
|||||||||||
10.01.2023, 14:54 | Malcang | Auf diesen Beitrag antworten » | |||||||||
Ich habe nun alles verstanden bis auf diese Eindeutigkeit. Ist es so trivial und ich übersehe es? Wahrscheinlich, denn mein Ansatz das nachzuvollziehen ist: Angenommen, es gibt und das ist doch schon wieder viel zu weit.... |
|||||||||||
10.01.2023, 15:06 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Verstehe ich das richtig? Du willst als Test dafür, ob eine Quadratzahl ist folgenden Algorithmus nehmen:
Ich kenne jetzt nicht den algorithmischen Aufwand zur Bestimmung von , und möglicherweise kommt man bei Nichtquadratzahlen auch sehr bald zu einer -1. Aber sollte doch mal eine Quadratzahl damit geprüft werden, und dieses sehr groß sein, dann ist der Algorithmus-Aufwand mit ja der reinste Horror. Da sollte man meinen, dass ein einfacher Wurzelalgorithmus schneller ist, zumal wir ja nicht mal , sondern nur die Integerzahl benötigen und dann auf prüfen. ------------------------------------------------- Zu deiner letzten Nachfrage: Also ein wenig Grundwissen in Modulrechnung bzw. der primen Restklassengruppe setze ich schon voraus: Dass die LINEARE Kongruenz eindeutig bzgl. lösbar ist, weil die dazu notwendig und hinreichende Bedingung erfüllt ist. |
|||||||||||
10.01.2023, 15:14 | Malcang | Auf diesen Beitrag antworten » | |||||||||
Natürlich... das war mir nichtmal fremd und trotzdem hab ich daran nicht gedacht HAL, ich danke dir vielmals für deine Mühen, das hat mich heute ein großes Stück weitergebracht.
Ja, das war meine Idee. Aber wie du siehst, ist Komplexitätstheorie absolut nicht meine Stärke. Ich war der Meinung, dass das Überprüfen auf Quadratzahlen mithilfe eines Skriptes doch fehleranfällig ist, da ja bei großen Zahlen (und deren Wurzeln) dann doch Fehler auftreten können. |
|||||||||||
10.01.2023, 15:52 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Über welche Zahlengrößen reden wir denn, und welche Programmiersprachen? Also Python rechnet z.B. sei Version 3 (oder gar noch etwas früher) mit beliebig genauen Integerzahlen, so dass die Überprüfung von kein Problem sein dürfte, eher schon das math.sqrt(n), weil dort die begrenzenden 53 Bit Mantisse des 64Bit-Floatingpointformats durchschlagen. Eine reine Integerlösung, die letztgenanntes Problem umgeht:
|
|||||||||||
10.01.2023, 15:58 | Malcang | Auf diesen Beitrag antworten » | |||||||||
Ich programmiere in python. Über eine Zahlengröße habe ich nicht nachgedacht. Ich stelle meine Fragen gedanklich ja auf den Bosmatest ab, was ich sicherlich hier nochmal hätte nennen sollen. Daher habe ich mir keine Obergrenze in meinen Überlegungen gesetzt. |
|||||||||||
10.01.2023, 16:10 | IfindU | Auf diesen Beitrag antworten » | |||||||||
Python unterstützt wohl seit 3.8 genau so eine Funktion isqrt: Docs. Soweit ich gelesen habe unterstützt diese beliebig-großen Integer-Input. Bei StackOverflow gibt es auch einen Performance-Vergleich zwischen verschiedenen Implementationen. D.h. man muss es nicht selbst implementieren und kann diese direkt nutzen. |
|||||||||||
10.01.2023, 16:12 | Malcang | Auf diesen Beitrag antworten » | |||||||||
RE: Jacobisymbol ergibt nur 0 oder 1 Mir ist gerade noch etwas eingefallen. Meine Frage war ja
Jetzt ist mir eingefallen, dass 0 als Ergebnis doch ohnehin nicht rauskommt, was ja auch aus deinem Beweis hervorgeht, HAL. Ich weiß aber ja auch, dass ich modulo jeweils quadratische Reste und Nichtreste finde, für p ungerade Primzahl. Sollte ich also erhalten für , so kann ich doch die Primalität an dieser Stelle bereits ausschließen, oder? |
|||||||||||
10.01.2023, 16:14 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Peinlich, dabei habe ich 3.8.5 installiert. Bin aber wohl gedanklich noch oft bei früheren Versionen. Gut, also einfach m=math.isqrt(n) ab Python 3.8, oder noch schneller m=gmpy2.isqrt(n). Für deinen Zweck der bloßen Feststellung "Quadratzahl oder nicht" scheint dann aber gmpy2.is_square(n) das optimale Mittel der Wahl zu sein. |
|||||||||||
10.01.2023, 16:19 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
RE: Jacobisymbol ergibt nur 0 oder 1
Wieso soll 0 nicht vorkommen können? Immer dann, wenn und nicht teilerfremd sind, kommt doch 0 heraus - ganz egal, ob Quadratzahl ist oder nicht. Und mein Beweis befasst sich doch überhaupt nicht mit allen , sondern konstruiert ein ganz spezielles , welches per Konstruktion zu teilerfremd ist. |
|||||||||||
10.01.2023, 16:24 | Malcang | Auf diesen Beitrag antworten » | |||||||||
RE: Jacobisymbol ergibt nur 0 oder 1
Ja, wieder mal unsauber gelesen. Ich war beim Fall n ist Primzahl. Sorry für das Durcheinander. |
|||||||||||
10.01.2023, 16:37 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Ursprünglich wollte ich die obige Methode "Quadratzahltest mit Jacobi-Symbolen" charakterisieren durch "mit Kanonen auf Mikroben schießen". Aber angesichts der Performance von gmpy2.isqrt ist diese Beschreibung wohl unzureichend drastisch. |
|||||||||||
10.01.2023, 21:32 | Finn_ | Auf diesen Beitrag antworten » | |||||||||
Die Bisektion kann man als eines der Arbeitspferde unter den numerischen Verfahren betrachten, verhält sie sich doch gutmütig, unkompliziert und einigermaßen schnell. Auch hier bietet sie eine leichter fassbare Alternative.
|
|||||||||||
10.01.2023, 22:25 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Für große eher nicht. Hab mal paar Performancemessungen gemacht für : gmpy2.isqrt : 0.00012s math.isqrt : 0.00034s heron (s.o.): 0.019s (18 Iterationen) Bisektion : 4.92s (32223 Iterationen) |
|||||||||||
12.01.2023, 18:03 | Finn_ | Auf diesen Beitrag antworten » | |||||||||
Analyse des Heron-Verfahrens. Nachgewiesen wird die partielle Korrektheit. Zum Nachweis der totalen Korrektheit müsste man zusätzlich prüfen, dass das Verfahren terminiert, also nicht in eine endlose Schleife oder Ausnahme läuft.
Rechnung zu den Zusicherungen. Es sei Die Gleichung erhält man als Spezialisierung und aus Für gilt womit die Schleifeninvariante nach der Zuweisung erhalten bleibt. Durch äquivalente Umformung von erhält man nämlich die Ungleichung Mit erhält man außerdem Wir haben mit also die für äquivalent zu umgeformt wird. Insgesamt gilt somit beim Verlassen der Funktion wie gewünscht Schließlich ist noch zu prüfen, ob die Schleifeninvariante auch beim Eintritt in die Schleife gilt. Mit der Definition ist das die Ungleichung Wir logarithmieren sie zu Wegen genügt die Bestätigung von Sie wird äquivalent umgeformt zu Die ist ja wegen erfüllt. |
|||||||||||
26.01.2023, 18:09 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Um mal im allgemein vorherrschenden Hype mitzuschwimmen, habe ich mich auch mal zu ChatGPT begeben und dort was mathematisches gefragt: Kannst du mir das quadratische Reziprozitätsgesetz erklären? Es folgten ein paar Allgemeinplätze (soweit Ok) zum Jacobi-Symbol, aber überhaupt nichts zum eigentlichen Gesetz. Daher habe ich nachgebohrt: Das ist nur ein grober Überblick über das Gesetz - und ungenügend. Dann kam ein etwas längerer Absatz, aus dem ich nun zitiere:
Blöd nur, dass das i.a. falsch ist. Sind a,b verschiedene ungerade Primzahlen mit , so ist quadratischer Rest modulo , was wiederum heißt, dass die Kongruenz genau 2 Lösungen besitzt, nicht . Letzteres ist lediglich die Anzahl der quadratischen Reste modulo . Auf diese lockere Art "kombiniert" also ChatGPT die aus irgendwelchen Texten zusammengeklaubten Fakten forsch zu solchen neuen interessanten Aussagen. Schöne neue Welt. |
|||||||||||
27.01.2023, 09:55 | Malcang | Auf diesen Beitrag antworten » | |||||||||
Guten Morgen, sehr interessant, HAL 9000. Witzigerweise habe ich selbst erst gestern von ChatGPT erfahren und wollte es mir heute mal anschauen. Ich frage mich gerade, was wohl passiert, wenn ich dem Bot sage, er solle mir den Beweis der Goldbachvermutung liefern. Wird der mir sagen, was die Vermutung ist? Oder wird er sogar auf den Fakt zurückgreifen, dass sie möglicherweise unentscheidbar ist? Na toll...die Zeiten, in denen man sich ohne Telefonnummer irgendwo anmelden konnte, sind wohl vorbei. |
|||||||||||
27.01.2023, 10:04 | IfindU | Auf diesen Beitrag antworten » | |||||||||
Provide the proof of the Goldbach Conjecture liefert
Auf die Nachfrage "That is not a proof, please provide a proof" bleibt es hartknäckig
|
|||||||||||
27.01.2023, 10:12 | Malcang | Auf diesen Beitrag antworten » | |||||||||
Zugegeben, ich kenne mich natürlich nicht damit aus. Aber die Datenbank scheint also zu "wissen", dass die Goldbach-Vermutung unbewiesen ist, bringt aber Unsinn beim Jacobisymbol raus. |
|||||||||||
17.03.2024, 19:55 | Malcang | Auf diesen Beitrag antworten » | |||||||||
HAL, bitte sei nicht sauer dass ich das hier nochmal hervorkrame. ist auch nur eine Winzigkeit, versprochen:
Müsste ich für nicht einen Repräsentanten der Restklassen und wählen, da es ja Restklassen sind? |
|||||||||||
18.03.2024, 15:43 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Na mit und sind doch Repräsentanten gemeint - verstehe jetzt dein Problem nicht. Wichtig ist allerdings, dass - je nach Wahl des Repräsentanten - die Restklasse modulo , aus der dann stammt auch anders ausfallenn kann! Daher kann man von vornherein bei diesem Zugang nicht davon ausgehen, dass Repräsentant unabhängig von Zahl gewählt wird - nein, der ist sehr wohl davon abhängig!!! Zugegeben ist das oben wohl nicht so deutlich rübergekommen, dass wirklich als ganze Zahl und nicht als Restklasse zu betrachten ist Vielleicht mal an einem Beispiel durchrechnen: . Dann ist und . 1) Wählen wir Nichtrest , dann hat die Lösung und wir bekommen . 2) Wählen wir aber Nichtrest , dann hat die andere Lösung . Allerdings ist das (zufällig oder nicht) dieselbe Zahl. Ok, ich hätte das ganze auch anders ausdrücken können: Für einen vorgegebenen Nichtrest besitzt das Kongruenzsystem genau eine Lösung (der Teilerfremdheit von wegen), einfach per Chinesischem Restsatz. Der von mir oben gewählte Weg führt die Berechnung einer solchen Lösung eben sogar explizit aus. |
|||||||||||
18.03.2024, 17:58 | Malcang | Auf diesen Beitrag antworten » | |||||||||
Danke sehr HAL dass du dir nochmal die Zeit nimmst. Ich weiß zwar worauf es hinausläuft und ich habe es auch verstanden, aber ich "stoße" mich halt an einer Sache:
Nehmen wir mal 1): Wir bekommen als Lösung heraus. Um damit zu bilden, wählen wir aber nicht die Restklasse, sondern den Repräsentanten Das ist so ein bisschen mein Problem, dass ich hier streng genommen den Formalismus verlasse. Sorry wenn ich da so oft nachhake.. Edit: Ich glaub ich hab's. Ich tue mir immer wieder schwer mit dem Formalismus, aber ich habe es jetzt so aufgeschrieben: [attach]57660[/attach] |
|