\
Sei p eine Primzahl und seien a, b, c ganze Zahlen so, dass a und b^2-4ac nicht durch p teilbar sind.
Man zeige:
sum(((ak^2+bk+c)/p),k=1,p) = - (a/p)


Hierbei ist (x/p) das sogenannte Legendre-Symbol, also:
(x/p) = 0 wenn x durch p teilbar ist.
(x/p) = 1 wenn x ein quadratischer Rest modulo p ist, also wenn es eine nicht durch p teilbare ganze Zahl z gibt, so dass z^2-x durch p teilbar ist.
(x/p) = -1 sonst.

 \zeta X 

\
Hallo,

hab mir hier folgendes überlegt:

Da a nicht durch p teilbar ist und p eine ungerade Primzahl sei (den Fall p=2 möchte ich vorerst nicht berücksichtigen), gibt es mod p zu a sowie zu 2 ein inverses Element! 
Diese inversen Elemente werde ich in der Bruchschreibweise darstellen. Hierbei handelt es sich also um keine Legendre Symbole!
Modulo p gilt also:
f(k):=ak^2+bk+c==a(k^2+b/a*k+b^2/(4a^2)-b^2/(4a^2)+c/a)==a((k+b/(2a))^2-b^2/(4a^2)+c/a)

Also gilt wegen der Multiplikativität des Legendre Symbols:

S:=sum((f(k)/p),k=1,p)= (a/p)*sum((((k+b/(2a))^2-b^2/(4a^2)+c/a)/p),k=1,p) 

Mit n:=k+b/2a und weil über ein vollständiges Restesystem 
mod p summiert wird, gilt:
S=(a/p)*sum(((n^2-b^2/(4a^2)+c/a)/p),n=1+b/2a,p+b/2a)= (a/p)*sum(((n^2-b^2/(4a^2)+c/a)/p),n=1,p)

Sei nun z eine Primitivwurzel mod p mit z^r=b^2/(4a^2)-c/a (da b^2-4ac nicht durch p teilbar sein soll ist dies auch möglich), so gilt:
S= (a/p)*sum(((n^2-z^r)/p),n=1,p)


Fall A: r ist gerade, es gilt also z^r=u^2:
S= (a/p)*sum(((n^2-u^2)/p),n=1,p)= (a/p)*sum((((n-u)*(n+u))/p),n=1,p) 

Nun sei j:= n-u. Man beachte wieder, dass wir über einem vollständigen Restesystem mod p summieren!
S= (a/p)*sum((((j)*(j+2u))/p),j=1-u,p-u)=
=  (a/p)*sum((((j)*(j+2u))/p),j=1,p)=
=  (a/p)*sum((((j)*(j+2u))/p),j=1,p-1)=

Da wir nun über einem primen Restesystem mod p summieren, sei j^(-1) das Inverse zu j. 
Man beachte außerdem, dass (j^(-1)/p)^2=1 gilt!
S= (a/p)*sum((((j^(-1))^2*(j)*(j+2u))/p),j=1,p-1)=
=  (a/p)*sum(((1+2u*j^(-1))/p),j=1,p-1)
Da hier j ein primes Restesystem durchläuft, durchläuft dies auch j^(-1). Somit durchläuft aber der Ausdruck 1+2u*j^(-1) bis auf die 1, alle Reste mod p.
Wegen sum((i/p),i=1,p)=0 folgt,
S= (a/p)*(0-(1/p))=-(a/p)


Fall B folgt sofort!

Gruß
Stefan

\
Fall B: r ist ungerade, z^r ist also ein quadratischer Nichtrest mod p. (Schließlich haben wir für gerade r bereits (p-1)/2 inkongruente Reste gefunden. Da es aber nicht mehr Reste gibt, folgt die Behauptung.)
Wir beginnen direkt vor Fall A. Weil nun über ein vollständiges primes Restesystem mod p summiert wird, gilt wiederum:
S= (a/p)*sum(((n^2-z^r)/p),n=1,p-1)+(a/p)*((p^2-z^r)/p) = 
=(a/p)*sum((((z^i)^2-z^r)/p),i=1,p-1)+(a/p)*((-z^r)/p) =
=(a/p)*(z^r/p)(sum(((z^(2i-r)-1)/p),i=1,p-1)+((-1)/p)) =
=-(a/p)*(sum(((z^(2i-r)-1)/p),i=1,p-1)+((-1)/p))

Bei  E:=sum(((z^(2i-r)-1)/p),i=1,p-1)+((-1)/p)  bleibt folglich nur noch E=1 zu zeigen.

Wegen  2j-r==2k-r  mod (p-1) <=> j==k  mod (p-1)/2  folgt:

E=2*sum(((z^(2i-r)-1)/p),i=1,(p-1)/2)+((-1)/p)

Da r ungerade ist, durchläuft z^(2i-r) für i=1 bis (p-1)/2 alle quadratischen Nichtreste mod p!
z^(2i-r)-1 ist nun genau dann quadr. Nichtrest mod p, wenn das Paar ((z^(2i-r)-1),(z^(2i-r))), ein Paar sukzessiver Nichtreste ist. Von diesen Paaren  gebe es unterhalb p genau N Stück, dann gilt:

sum(((z^(2i-r)-1)/p),i=1,(p-1)/2)= (p-1)/2-2N

Dies ist richtig, weil dort in der Summe jeder Summand entweder 1 oder aber gleich -1 ist. 0 ist nicht möglich, da z^(2i-r) immer ein Nichtrest und somit ungleich 1 ist.

Für E=1, bleibt also nur noch 1=p-1-4N+((-1)/p) bzw. 4N=p-2+((-1)/p) zu zeigen.


Da  (1/4)((t/p)-1)(((t+1)/p)-1) für t von 1 bis p-2 genau dann gleich 1 ist, falls t und t+1 gleichzeitig Nichtreste sind, ansonsten aber gleich 0 ist, gilt:

4N=sum((((t/p)-1)(((t+1)/p)-1)),t=1,p-2)=
= sum(((t(t+1))/p),t=1,p-2)-sum((t/p),t=1,p-2)-sum(((t+1)/p),t=1,p-2)+p-2

Beachtet man nun noch, dass der erste Ausdruck unter Fall A fällt und sum((t/p),t=1,p)=0 gilt, so folgt:
4N=-1-(0-((-1)/p))-(0-(1/p))+p-2=p-2+((-1)/p)
Dies war zu zeigen.


Warum ist das eigentlich alles so lang? Liegt das an einem Fehler oder an meinem Ungeschick? Oder gar beides...

Gruß,
Stefan

\
Sei S die gesuchte Summe. Wir können sicherlich p>2 annehmen.
Wir berechnen zuerst S \mod p. Dazu nutzen wir aus, dass (x/p) == x^((p-1)/2) \mod p ist (Eulersches Kriterium).


Lemma:
Sei m ganz und 0 <= m < p-1. Dann ist sum(x^m,x=1,p) == 0 \mod p.
Beweis:
Die Gleichung z^m == 1 \mod p hat \mod p höchstens m verschiedene Lösungen. Insbesondere gibt es wegen m+1 < p mindestens ein z mit z !== 0 \mod p und z^m !== 1 \mod p.
Wegen z !== 0 \mod p durchlaufen mit x auch die Zahlen z*x alle Restklassen \mod p, es gilt also
sum(x^m,x=1,p) == sum((zx)^m,x=1,p) = z^m * sum(x^m,x=1,p) \mod p
was nach Umformen nun
(z^m - 1) * sum(x^m,x=1,p) == 0 \mod p
liefert. Da der linke Faktor nicht == 0 \mod p ist, muss also sum(x^m,x=1,p) == 0 \mod p sein, was wir zeigen wollten.



Nun zurück zur Aufgabe:
Es ist nach dem schon erwähnten Euler-Kriterium ist ((ax^2+bx+c)/p) == (ax^2+bx+c)^((p-1)/2) \mod p, wobei (ax^2+bx+c)^((p-1)/2) = d_(p-1) x^(p-1) + ... + d_1 x + d_0 = sum(d_i x^i,i=0,p-1) \mod p ein Polynom vom Grad p-1 ist. Dabei ist der Leitkoeffizient d_(p-1) = a^((p-1)/2) == (a/p) \mod p.
Dies liefert nun
S = sum(((ax^2+bx+c)/p),x=1,p) == sum((ax^2+bx+c)^((p-1)/2),x=1,p) = sum(sum(d_i x^i,i=0,p-1),x=1,p) = sum(sum(d_i x^i,x=1,p),i=0,p-1) \mod p.
Allerdings verschwinden nach dem Lemma alle Summen mit i < p-1, es gilt also
S == sum(sum(d_i x^i,x=1,p),i=0,p-1) == sum(d_(p-1) x^(p-1),x=1,p) == (a/p) * sum(x^(p-1),x=1,p-1) == (p-1)*(a/p) == -(a/p) \mod p,
der vorletzte Schritt nach dem Satz von Fermat.
Also gilt die geforderte Gleichung \mod p. Alle vorkommenden der p Summanden sind 0,1 oder -1, es ist also -p <= S <= p. Angenommen, die Gleichung würde in den ganzen Zahlen nicht gelten, so müsste S = (p-1)*(a/p) sein, da alle anderen Restklassenvertreter betragsmäßig zu groß wären (man beachte, das hier (a/p) != 0 verwendet wurde).
S ist also gerade. Das heißt, eine ungerade Anzahl (genauer gesagt: einer) der p Summanden ((ax^2+bx+c)/p) in sum(((ax^2+bx+c)/p),x=1,p) muss gerade, also 0 sein. Dies wiederrum heißt, dass ax^2+bx+c == 0 \mod p ist. Nun haben quadratische Polynome mit Diskriminante b^2-4ac !== 0 \mod p aber nur 0 oder 2 Nullstellen \mod p, also sicher nicht ungeradzahlig viele, Widerspruch. Die Annahme war also falsch und es ist doch S = -(a/p).

\
\# menge((x,y)\el\IF_p^2|y^2=x^2+c)=p-1.

\
x = (u-c/u)/2, y = (u+c/u)/2 $ für u\el\IF_p^(\void\times\void)