| Autor |
Beitrag |
    
Carmichael (Carmichael)
| | Veröffentlicht am Donnerstag, den 18. Oktober, 2001 - 14:32: | 
|
Hallo,
Es sei eine Quadratzahl a und eine Primzahl p gegeben.
Man bestimme in Abhängigkeit von p die Wahrscheinlichkeit dafür, dass es eine Zahl z der Form 2*b^2 + 1 gibt, so dass z-a durch p teilbar ist.
Viel Spass :-) |
Rudolf
| | Veröffentlicht am Samstag, den 20. Oktober, 2001 - 11:38: |
|
Hallo Carmichael!
Ich vertehe nicht ganz, was du unter "Wahrscheinlichkeit in Abhängigkeit von p" verstehst. Ob ein z mit den angegebenen Eigenschaften existiert kann doch nur wahr (W=1) oder falsch (W=0) sein. Dies hängt aber nicht nur von p sondern auch von der gegebenen Quadratzahl a ab.
So gilt zum Beispiel für p=5, dass ein derartiges z dann und nur dann existiert, wenn a nicht durch 5 teilbar ist.
Für p=7 existiert ein derartiges z genau dann, wenn a (mod 7) 1 oder 2 ist.
Für p=11 gibt es wieder genau dann kein derartiges z, wenn a (mod 11) 4 oder 5 ist.
Gruß, Rudolf |
Carmichael (Carmichael)
| | Veröffentlicht am Samstag, den 20. Oktober, 2001 - 12:39: |
|
Hi Rudolf,
"Für p=7 existiert ein derartiges z genau dann, wenn a (mod 7) 1 oder 2 ist. " Wie wahrscheinlich ist es denn dass a (mod 7) 1 oder 2; ist doch genau 2/7. Also wenn p=7, dann ist die gesuchte Wahrscheinlichkeit 2/7.
Bei 11 wäre sie 2/11 (a (mod 11) 4 oder 5) ist.
Jetzt ist allg. die Wahrscheinlichkeit gesucht (in Abhängigkeit von p).
Jetzt dürfte es klar sein oder ? |
Rudolf
| | Veröffentlicht am Samstag, den 20. Oktober, 2001 - 17:51: |
|
Hallo Carmichael!
Ich weiß jetzt wie du es meinst, nur deine Werte für p=7 und p=11 stimmen nicht.
a als Quadratzahl kann modulo 7 nur einen von 4 Werten haben. Da es nur für 1 und 2 Lösungen gibt ist W=1/2.
a als Quadratzahl kann modulo 11 nur einen von 6 Werten haben. Da es nur für 4 und 5 keine Lösungen gibt ist W=2/3.
Hier noch eine kleine Tabelle mit den möglichen Werten für a (mod p) und für welche es eine Lösung gibt:
| p | a (mod p) | Lösung für | W | | 2 | 0,1 | 1 | 1/2 | | 3 | 0,1 | 0,1 | 1 | | 5 | 0,1,4 | 1,4 | 2/3 | | 7 | 0,1,2,4 | 1,2 | 1/2 | | 11 | 0,1,3,4,5,9 | 0,1,3,9 | 2/3 |
Sieht nicht so aus, als ob es eine allgemeine Formel für W(p) gäbe.
Gruß, Rudolf |
Carmichael (Carmichael)
| | Veröffentlicht am Samstag, den 20. Oktober, 2001 - 18:21: |
|
Ja du hast recht, es ist ja bekannt, dass a eine Quadratzahl ist. Nichtdestotrotz verändert dies die die Aufgabenstellung nicht wesentlich, da die Anzahl der quad. Reste modulo Primzahl p immer (p+1)/2 ist.
Es gibt schon eine allg. Formel, ich hab mir die Aufgabe nicht willkürlich ausgedacht.
Probier noch etwas rum und viel spass dabei :-)
MfG! |
Rudolf
| | Veröffentlicht am Sonntag, den 21. Oktober, 2001 - 08:17: |
|
Hallo Carmichael!
Herumprobieren ist zwar keine Methode, kann aber ganz nützlich sein, um zu sehen, ob es überhaupt etwas zu beweisen gibt.
2 als einzige gerade Primzahl möge als Ausnahme nicht betrachtet werden. Für die ungeraden Primzahlen habe ich folgendes herausbekommen:
Ich vermute, dass immer dann, wenn (p+1)/2 ungerade ist W=(p+3)/[2*(p+1)] gilt. Ist (p+1)/2 jedoch gerade, so ist W entweder 1/2 (für p=7,23,31,..) oder (p+5)/[2*(p+1)] (für p=3,11,19,...).
Eine Formel für W (falls es eine gibt) ist daher sicher kein analytischer Ausdruck und dürfte nicht ohne Fallunterscheidungen oder sonstigen Tricks auskommen.
Da du behauptest, es gibt eine solche, würde mich schon sehr interessieren, wie die aussieht und ob sie wirklich in allen Fällen das richtige Ergebnis liefert.
Gruß, Rudolf |
Carmichael (Carmichael)
| | Veröffentlicht am Sonntag, den 21. Oktober, 2001 - 10:50: |
|
Hallo Rudolf,
Herumprobieren kann gerade in der Zahlentheorie sehr oft eine Methode sein!, ich mach es selbst viel zu selten.
Deine angegeben Formel ist richtig. (Eine Formel mit ein paar Fallunterscheidungen ist meiner Meinung nach sehr wohl eine Formel)
Jetzt musst du die Formel nur noch beweisen (die eigentliche Schwierigkeit).
Und: Es gibt einen Beweis! ich habs schon bewiesen. |
Rudolf
| | Veröffentlicht am Sonntag, den 21. Oktober, 2001 - 11:12: |
|
Glaub ich dir gerne, dass es einen Beweis gibt, vielleicht sogar mehrere. Gibt es eine Gesetzmäßigkeit, dann gibt es auch einen Beweis. Ich werde schon einen finden, hab nur im Augenblick Dringenderes zu tun und muss die Sache aufschieben.
MfG, Rudolf |
Carmichael (Carmichael)
| | Veröffentlicht am Montag, den 22. Oktober, 2001 - 14:09: |
|
Hab nochmal etwas drüber nachgedacht und mir ist aufgefallen, dass unsere Formeln leider noch nict ganz korrekt sind. Problem: Der quad. Rest 0 ist weniger wahrscheinlich( z.b. a^2 = 0 mod p <=> a = 0 mod p; a^2 = 1 mod p <=> a = +-1 mod p)
Ich komm somit jetzt auf folgende Wahrscheinlichkeiten:
p = 8k +/- 1: W(p) = (p+1)/2p;
p = 8k +/- 3: W(p) = (p+3)/2p:
Ich hoffe das passt jetzt (größtenteils).
MfG, Carmichael |
Rudolf
| | Veröffentlicht am Montag, den 22. Oktober, 2001 - 21:16: |
|
Ich möchte nicht spitzfindig sein, aber es macht doch einen Unterschied, wie die Aufgabenstellung formuliert ist.
Du schreibst, gegeben ist eine Quadratzahl a und fragst nach der Wahrscheinlichkeit, dass z-a durch p teilbar ist. In der Menge der Quadratzahlen treten aber alle möglichen Residuen, (p+1)/2 an der Zahl, periodisch und daher mit gleicher Wahrscheinlichkeit auf.
Hättest du geschrieben, gegeben sei eine Zahl a und nach der Wahrscheinlichkeit gefragt, dass z-a^2 durch p teilbar ist, dann tritt als Residuum von a^2 die 0 tatsächlich nur halb so häufig auf wie die anderen.
MfG, Rudolf |
Carmichael (Carmichael)
| | Veröffentlicht am Dienstag, den 23. Oktober, 2001 - 16:43: |
|
Ja, stimmt auch wieder, wie auch immer man es ließt. |
Carmichael (Carmichael)
| | Veröffentlicht am Dienstag, den 23. Oktober, 2001 - 16:52: |
|
Nein, stimmt nicht!
Die Reste kommen nicht gleichverteilt daher.
Beispiel: p = 5
Quadratzahl:
1, 4, 9, 16, 25, 36, 49
Reste:
1, 4, 4, 1, 0, 1, 4, ...
1 und 4 doppelt sooft wie 0.
a ist eine Quadratzahl und nimmt mit höherer Wahrscheinlichkeit den Rest 1 an als 0, oder seh ich das falsch so ? |
Rudolf
| | Veröffentlicht am Dienstag, den 23. Oktober, 2001 - 22:24: |
|
Da hast du auch wieder recht. Das mit der Periode stimmt schon, nur ist die Periodenlänge gleich p, außer 0 kommen aber alle Reste gespiegelt an der Null zweimal pro Periode vor. (Gilt übrigens für alle ungeraden Primzahlen, nicht nur für 5.)
Gruß, Rudolf |
|
