Paare von Quadratresten < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:43 Mo 12.12.2011 | | Autor: | briddi |
| Aufgabe | Finde eine Formel für die Anzahl der a [mm] \in [/mm] {1,2,...,p-1} (p Primzahl ungleich 2) mit
[mm] (\bruch{a}{p})=-(\bruch{a+1}{p})=1
[/mm]
(imitiere den Beweis von Satz ... ) |
Hallo,
zunächst einmal glaube ich, dass a den Wert p-1 nicht annehmen kann, da dann die Aussage eh nicht stimmt, weil (p-1+1)=p und damit [mm] (\bruch{p-1+1}{p})=0, [/mm] stimmt das?
Der Satz, den wir nutzen sollen ist der folgende:
Für Q(p)=#{a mod p mit [mm] (\bruch{a}{p})=(\bruch{a+1}{p})=1, [/mm] 0<a<p-2} also die Anzahl der aufeinanderfolgenden Quadratreste gilt:
[mm] Q(p)=\bruch{1}{4}*(p-4+(-1)^\bruch{p+1}{2}).
[/mm]
Rechnet man nun einige Beispiele, so sieht man, dass Q(p) immer um 1 kleiner ist, als die Anzahl der Elemente, die wir bestimmen sollen in der Aufgabe (bezeichne sie im Folgenden mit B(p). Also hab ich mir überlegt, dass gelten müsste:
[mm] B(p)=\bruch{1}{4}*(p+(-1)^\bruch{p+1}{2}).
[/mm]
Das soll ich ja nun aber auch beweisen.
Mein Problem ist, dass ich den Beweis dieses Satzes, der imitiert werden soll, nicht so wirklich verstehe, also mir ist unklar, warum er die Aussage beweist, vielleicht kann mir da jemand helfen.
Beweis zu [mm] Q(p)=\bruch{1}{4}*(p-4+(-1)^\bruch{p+1}{2}):
[/mm]
[mm] 1/4*(1+(\bruch{a}{p}))*(1+(\bruch{a+1}{p}))=\begin{cases} 0, & \mbox{für } (\bruch{a}{p})=(\bruch{a+1}{p})=1 \\ 1, & \mbox{sonst } \end{cases}
[/mm]
(das ist mir so klar, dass das gilt, aber wozu braucht man das? bzw. wie kommt man darauf (ich soll das ja imitieren)...)
[mm] \Rightarrow 4*Q(p)=\summe_{a=1}^{p-2} (1+(\bruch{a}{p}))*(1+(\bruch{a+1}{p}))
[/mm]
= p-2 + [mm] \summe_{a=1}^{p-2} (\bruch{a}{p}) [/mm] + [mm] \summe_{a=2}^{p-1} (\bruch{a}{p}) [/mm] + [mm] \summe_{a=1}^{p-2} (\bruch{a}{p})(\bruch{a+1}{p})
[/mm]
Auch die Umformung der Summen ist mir klar, das kann man durch Ausmultiplizieren nachvollziehen, aber warum ist das gleich 4*Q(p)? Und wieso beweist das jetzt die Aussage?
Wär wirklich toll, wenn mir da jemand helfen könnte, ich finde zu diesem Thema leider keine passende Literatur und weiß mir grad irgendwie nicht mehr zu helfen.
Danke,
briddi
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:10 Mo 12.12.2011 | | Autor: | felixf |
Moin briddi!
> Finde eine Formel für die Anzahl der a [mm]\in[/mm] {1,2,...,p-1}
> (p Primzahl ungleich 2) mit
> [mm](\bruch{a}{p})=-(\bruch{a+1}{p})=1[/mm]
>
> (imitiere den Beweis von Satz ... )
>
> Hallo,
>
> zunächst einmal glaube ich, dass a den Wert p-1 nicht
> annehmen kann, da dann die Aussage eh nicht stimmt, weil
> (p-1+1)=p und damit [mm](\bruch{p-1+1}{p})=0,[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
stimmt das?
>
> Der Satz, den wir nutzen sollen ist der folgende:
> Für Q(p)=#{a mod p mit [mm](\bruch{a}{p})=(\bruch{a+1}{p})=1,[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
> 0<a<p-2} also die Anzahl der aufeinanderfolgenden
> Quadratreste gilt:
> [mm]Q(p)=\bruch{1}{4}*(p-4+(-1)^\bruch{p+1}{2}).[/mm]
Genau.
> Rechnet man nun einige Beispiele, so sieht man, dass Q(p)
> immer um 1 kleiner ist, als die Anzahl der Elemente, die
> wir bestimmen sollen in der Aufgabe (bezeichne sie im
> Folgenden mit B(p). Also hab ich mir überlegt, dass gelten
> müsste:
> [mm]B(p)=\bruch{1}{4}*(p+(-1)^\bruch{p+1}{2}).[/mm]
>
> Das soll ich ja nun aber auch beweisen.
>
> Mein Problem ist, dass ich den Beweis dieses Satzes, der
> imitiert werden soll, nicht so wirklich verstehe, also mir
> ist unklar, warum er die Aussage beweist, vielleicht kann
> mir da jemand helfen.
>
> Beweis zu [mm]Q(p)=\bruch{1}{4}*(p-4+(-1)^\bruch{p+1}{2}):[/mm]
>
> [mm]1/4*(1+(\bruch{a}{p}))*(1+(\bruch{a+1}{p}))=\begin{cases} 0, & \mbox{für } (\bruch{a}{p})=(\bruch{a+1}{p})=1 \\ 1, & \mbox{sonst } \end{cases}[/mm]
Das ist doch genau andersherum! Der Ausdruck auf der linken Seite gibt 1, falls [mm] $(\bruch{a}{p})=(\bruch{a+1}{p})=1$ [/mm] ist, und 0 sonst!
> (das ist mir so klar, dass das gilt, aber wozu braucht man
> das? bzw. wie kommt man darauf (ich soll das ja
> imitieren)...)
Na, das (in der korrigierten Fassung) brauchst du doch gerade dafuer, dass folgende Gleichheit gilt:
> [mm]\Rightarrow 4*Q(p)=\summe_{a=1}^{p-2} (1+(\bruch{a}{p}))*(1+(\bruch{a+1}{p}))[/mm]
Da wird doch einfach ueber alle $a$ summiert; das Ergebnis ist $Q(p)$; wenn du das dann mit 4 multiplizierst ergibt sich das was hier steht.
> = p-2 + [mm]\summe_{a=1}^{p-2} (\bruch{a}{p})[/mm] +
> [mm]\summe_{a=2}^{p-1} (\bruch{a}{p})[/mm] + [mm]\summe_{a=1}^{p-2} (\bruch{a}{p})(\bruch{a+1}{p})[/mm]
>
> Auch die Umformung der Summen ist mir klar, das kann man
> durch Ausmultiplizieren nachvollziehen, aber warum ist das
> gleich 4*Q(p)?
Wie schon gesagt: wegen der Gleichung oben.
> Und wieso beweist das jetzt die Aussage?
Der Beweis ist noch lange nicht fertig!
Erstmal kannst du [mm] $\sum_{a=1}^{p-2} [/mm] (a/p) + [mm] \sum_{a=2}^{p-1} [/mm] (a/p) = 2 [mm] \sum_{a=1}^{p-1} [/mm] (a/p) - (1/p) - (-1/p)$ schreiben. Da 1 immer ein quadratischer Rest ist gilt $(1/p) = 1$, und $(-1/p) = [mm] (-1)^{(p-1)/2}$ [/mm] nach dem ![[]](/images/popup.gif) 1. Ergaenzungssatz.
Da von den $p-1$ Restklassen $1, [mm] \dots, [/mm] p-1$ genau $(p-1)/2$ ein quadr. Rest sind und $(p-1)/2$ keiner, ist [mm] $\sum_{a=1}^{p-1} [/mm] (a/p) = 0$: die Haelfte der Summanden ist 1, die andere Haelfte -1.
Damit hast du schonmal $4 Q(p) = p - 2 - 1 - [mm] (-1)^{(p-1)/2} [/mm] = = p - 3 + [mm] (-1)^{(p+1)/2}$.
[/mm]
Es fehlt noch der Term [mm] $\summe_{a=1}^{p-2} (\bruch{a}{p})(\bruch{a+1}{p})$. [/mm] Den muss man genauer untersuchen. Das sollte auch in deinem Beweis zu finden sein... Steht das da wirklich nicht?
> Wär wirklich toll, wenn mir da jemand helfen könnte, ich
> finde zu diesem Thema leider keine passende Literatur und
> weiß mir grad irgendwie nicht mehr zu helfen.
Schau in der Bibliothek nach Buechern mit "elementarer Zahlentheorie" im Titel.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:36 Di 13.12.2011 | | Autor: | briddi |
>
> > Rechnet man nun einige Beispiele, so sieht man, dass Q(p)
> > immer um 1 kleiner ist, als die Anzahl der Elemente, die
> > wir bestimmen sollen in der Aufgabe (bezeichne sie im
> > Folgenden mit B(p). Also hab ich mir überlegt, dass gelten
> > Beweis zu [mm]Q(p)=\bruch{1}{4}*(p-4+(-1)^\bruch{p+1}{2}):[/mm]
> >
> > [mm]1/4*(1+(\bruch{a}{p}))*(1+(\bruch{a+1}{p}))=\begin{cases} 0, & \mbox{für } (\bruch{a}{p})=(\bruch{a+1}{p})=1 \\ 1, & \mbox{sonst } \end{cases}[/mm]
>
> Das ist doch genau andersherum! Der Ausdruck auf der linken
> Seite gibt 1, falls [mm](\bruch{a}{p})=(\bruch{a+1}{p})=1[/mm] ist,
> und 0 sonst!
>
Mist, das war ein Schreibfehler, du hast natürlich Recht!
> > Und wieso beweist das jetzt die Aussage?
>
> Der Beweis ist noch lange nicht fertig!
>
> Erstmal kannst du [mm]\sum_{a=1}^{p-2} (a/p) + \sum_{a=2}^{p-1} (a/p) = 2 \sum_{a=1}^{p-1} (a/p) - (1/p) - (-1/p)[/mm]
> schreiben. Da 1 immer ein quadratischer Rest ist gilt [mm](1/p) = 1[/mm],
> und [mm](-1/p) = (-1)^{(p-1)/2}[/mm] nach dem
> 1. Ergaenzungssatz.
>
> Da von den [mm]p-1[/mm] Restklassen [mm]1, \dots, p-1[/mm] genau [mm](p-1)/2[/mm] ein
> quadr. Rest sind und [mm](p-1)/2[/mm] keiner, ist [mm]\sum_{a=1}^{p-1} (a/p) = 0[/mm]:
> die Haelfte der Summanden ist 1, die andere Haelfte -1.
>
> Damit hast du schonmal [mm]4 Q(p) = p - 2 - 1 - (-1)^{(p-1)/2} = = p - 3 + (-1)^{(p+1)/2}[/mm].
>
> Es fehlt noch der Term [mm]\summe_{a=1}^{p-2} (\bruch{a}{p})(\bruch{a+1}{p})[/mm].
> Den muss man genauer untersuchen. Das sollte auch in deinem
> Beweis zu finden sein... Steht das da wirklich nicht?
Leider ist das wirklich alles, was bei mir steht, deshalb war es für mich ja so unverständlich. Aber ich schau mir das dann nochmal an und frag gegebenfalls nochmal. Danke schonmal für die Erklärung
>
> > Wär wirklich toll, wenn mir da jemand helfen könnte, ich
> > finde zu diesem Thema leider keine passende Literatur und
> > weiß mir grad irgendwie nicht mehr zu helfen.
>
> Schau in der Bibliothek nach Buechern mit "elementarer
> Zahlentheorie" im Titel.
Ich find das hier so schwierig, weil ich kein richtiges Stichwort habe, hab aber zumindest jetzt ein Buch gefunden, wo das etwas genauer steht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:05 Di 13.12.2011 | | Autor: | felixf |
Moin!
> > Es fehlt noch der Term [mm]\summe_{a=1}^{p-2} (\bruch{a}{p})(\bruch{a+1}{p})[/mm].
> > Den muss man genauer untersuchen. Das sollte auch in deinem
> > Beweis zu finden sein... Steht das da wirklich nicht?
>
> Leider ist das wirklich alles, was bei mir steht, deshalb
> war es für mich ja so unverständlich. Aber ich schau mir
> das dann nochmal an und frag gegebenfalls nochmal. Danke
> schonmal für die Erklärung
In dem Fall ist der Beweis nicht wirklich vollstaendig.
Habt ihr eventuell diese Summe vorher schonmal ausgerechnet? In irgendeinem Lemma oder Satz oder so? (Manchmal wird nicht explizit auf sowas verwiesen...)
> > > Wär wirklich toll, wenn mir da jemand helfen könnte, ich
> > > finde zu diesem Thema leider keine passende Literatur und
> > > weiß mir grad irgendwie nicht mehr zu helfen.
> >
> > Schau in der Bibliothek nach Buechern mit "elementarer
> > Zahlentheorie" im Titel.
>
> Ich find das hier so schwierig, weil ich kein richtiges
> Stichwort habe, hab aber zumindest jetzt ein Buch gefunden,
> wo das etwas genauer steht.
"Elementare Zahlentheorie" und "quadratische Reste" sind meist gute Stichworte bei diesem Thema...
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:15 Di 13.12.2011 | | Autor: | briddi |
Weiter hinten in meinen Aufzeichnungen hab ich nun doch noch etwas passendes dazu gefunden, mir war nur nicht klar, dass das zu dem Beweis dazugehört, weil dazwischen noch ein anderer Satz steht, der nicht dazugehört...
Ich hab das jetzt fast verstanden, allerdings fehlt mir der letzte Schritt.
Die Summe, die noch fehlt kann man umschreiben:
[mm] \summe_{a=1}^{p-2} (\bruch{a*(a+1)}{p})=\summe_{a=1}^{p-1} (\bruch{a*(a+1)}{p}) [/mm] (weil ja vermutlich der Summand der hinzukommt Null ist)
Nimmt man nun das multiplikative Inverse a' zu a also: [mm] a*a'\equiv [/mm] 1 (p) ,dann ist das gleich:
[mm] =\summe_{a=1}^{p-1} (\bruch{a'}{p})^2*(\bruch{a*(a+1)}{p}) [/mm] (das ändert ja nichts, da der zugefügte Faktor 1 ist)
[mm] =\summe_{a=1}^{p-1} [/mm] ( [mm] \bruch{1+a'}{p}) [/mm] (bekommt man durch ausmultiplizieren)
=-1
Den allerletzten Schritt seh ich wieder nicht, warum muss das -1 sein?
Wenn ich das hab, kann ich hoffentlich auch endlich mit der richtigen Aufgabe anfangen... Ist meine Formel denn richtig gewesen?
[mm] B(p)=\bruch{1}{4}*(p+(-1)^{\bruch{p+1}{2}})
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:35 Di 13.12.2011 | | Autor: | felixf |
Moin!
> Weiter hinten in meinen Aufzeichnungen hab ich nun doch
> noch etwas passendes dazu gefunden, mir war nur nicht klar,
> dass das zu dem Beweis dazugehört, weil dazwischen noch
> ein anderer Satz steht, der nicht dazugehört...
Ah, gut :)
> Ich hab das jetzt fast verstanden, allerdings fehlt mir
> der letzte Schritt.
> Die Summe, die noch fehlt kann man umschreiben:
>
> [mm]\summe_{a=1}^{p-2} (\bruch{a*(a+1)}{p})=\summe_{a=1}^{p-1} (\bruch{a*(a+1)}{p})[/mm]
> (weil ja vermutlich der Summand der hinzukommt Null ist)
>
> Nimmt man nun das multiplikative Inverse a' zu a also:
> [mm]a*a'\equiv[/mm] 1 (p) ,dann ist das gleich:
> [mm]=\summe_{a=1}^{p-1} (\bruch{a'}{p})^2*(\bruch{a*(a+1)}{p})[/mm]
> (das ändert ja nichts, da der zugefügte Faktor 1 ist)
> [mm]=\summe_{a=1}^{p-1}[/mm] ( [mm]\bruch{1+a'}{p})[/mm] (bekommt man
> durch ausmultiplizieren)
> =-1
>
> Den allerletzten Schritt seh ich wieder nicht, warum muss
> das -1 sein?
Nun, [mm] $\sum_{a=1}^{p-1} [/mm] f(a')$ ist ja gleich [mm] $\sum_{a=1}^{p-1} [/mm] f(a)$ (fuer jede beliebige Funktion $f$ auf den Restklassen), da die Abbildung $a [mm] \mapsto [/mm] a'$ eine Bijektion von den Restklassen [mm] $\{ 1, \dots, p-1 \} \to \{ 1, \dots, p-1 \}$ [/mm] ist.
Weiterhin ist [mm] $\sum_{a=1}^{p-1} (\frac{1+a}{p}) [/mm] = [mm] \sum_{a=2}^{p-1} (\frac{a}{p}) [/mm] + [mm] (\frac{0}{p}) [/mm] = [mm] \sum_{a=1}^{p-1} (\frac{a}{p}) [/mm] - (1/p)$. Den Ausdruck [mm] $\sum_{a=1}^{p-1} (\frac{a}{p})$ [/mm] hatten wir schon, und $(1/p) = 1$.
> Wenn ich das hab, kann ich hoffentlich auch endlich mit der
> richtigen Aufgabe anfangen... Ist meine Formel denn richtig
> gewesen?
>
> [mm]B(p)=\bruch{1}{4}*(p+(-1)^{\bruch{p+1}{2}})[/mm]
Kann ich dir grad nicht sagen, dazu muesste ich die Aufgabe selber loesen 
Das wirst du aber auch sehen wenn du die Aufgabe loest. Entweder kommt das hier heraus oder eben nicht...
Du musst zuerst einen Ausdruck in [mm] $(\frac{a}{p})$ [/mm] und [mm] $(\frac{a+1}{p})$ [/mm] finden, der 0 oder 1 liefert und zweiteres nur, falls die Bedingung aus der Aufgabenstellung erfuellt ist. Das kannst du aehnlich machen wie bei dem Satz hier aus der Diskussion.
Danach summierst du ueber alle diese Ausdruecke und multiplizierst die Summanden wieder aus und verwendest die gleichen Identitaeten, evtl. leicht anders angewandt.
Dann solltest du auch so eine Formel erhalten, entweder die die du vermutest oder eben eine andere...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:08 Di 13.12.2011 | | Autor: | briddi |
Ganz lieben Dank, ich glaub sie stimmt :)
|
|
|
|
