Anzahl der verschiedenen quadratischen Reste mod p^n (p Prim). - War: Erfolgreicher Holzweg! ;-) ...

05/11/2010 - 17:00 von Siegfried - Siggi - Neubert | Report spam
On 29 Okt., 17:50, Siegfried - Siggi - Neubert <neub...@tu-harburg.de>
wrote unter "Erfolgreicher Holzweg! ;-) ...":

Moin moin.

Ich find einfach lustig, wie man auf einem "Holzweg" trotzdem
erfolgreich" sein kann!



...

>
#rQR(3,i)= [6 +9q^(i-1) +(-1)^(i-1)]/8

Und es z.B. gilt: A(3,i)= #rQR(3,i) *2
Auch hier kann der "geneigte Leser" ;-)
b, c und d für allgemeines q>2, Prim bestimmen.

Fazit: Ein erfolgreicher Holzwege
- welch Zufall(/Wunder? ;-) ) -,
der noch eine weiter explizite Lösung aufzeigt.

...
Aber dazu habe ich jetzt keine Lust mehr
- genauso wenig wie für die allg. Lösung #rQR(q,i) ;-) )



Hiermit nachgeliefert:

Sei

y=[(-1)^q/(q-1)+1/(q+1)]*(q-q mod 2)/2
x=[(-1)^q/(q-1)-1/(q+1)]*(q-q mod 2)/2
c=[(q+3)/(q+1)+(q-3)/(q-1)*(-1)^q]*(q-qmod2)/4

Damit ist die allg. Lösung (für alle q Prim!)

A(q,i)= c*^q^i +x*(i mod 2) +y(i+1 mod 2)

vollstàndig bestimmt!

(Wenn man mit konkreten Zahlen q rechnet,
ist der sich ergebene Algorithmus sehr einfach
Z.B. q=3 ==> c= 3/4, x= -3/4 und y= -1/4
A(3,i)= [ 3*3^i -3(i mod 2) -(i+1 mod 2) ]/4= ...)

Noch immer eine "hübsche?" allgemeine Lösung!
Deren Herleitung ich hier aber noch etwas ergànzend ausführen möchte
- _auch_ weil sie vormals fehlerbehaftet war!


Sei dabei A(q,i):= 2*(#rQR(3,i) -1),
wobei #rQR die Anzahl der real möglichen
Quadratischen Rest (Modul q^i).

"Mathematisch" Quadratischen Rest (QR) von Primzahlpotenzen p^n sind
ohne die Vielfachen von p definiert und es gilt die Anzahl #QR(p)(p+1)/2 - ansonsten siehe (google) unter Jacobi-Symbol.


In der QEIS-Folge A039300 unter
Anzahl der verschiedenen (r)QR modulo p^n
gibt Lekruj Beedassy für p>2 an:
s= s(n,p)=(p^(n+1)+p+2)/(2(p+1)), n gerade
s= s(n,p)=(p^(n+1)+2p+1)/(2(p+1)), n ungerade
Z.B.: q=5:
s(1,5)= 3, s(3,5)= 53, ...
s(0,5)= 1, s(2,5)= 11, ... )


Allg. gilt z.B. für q=2:
A(2,i)= (1) 2 2 4 6 12 22 62 ... ; i=(0),1,2,...
Bzw. für q=3:
A(3,i)= (0) 2 6 20 60 182 550 ... ; i=(0),1,2,...

Ich fand, alle diese Folgen (mit q Prim) lassen sich schreiben:

A(q,i+1)=q*A(q,i)-[(-1)^i+(-1)^q]*(q-q mod 2)/2

(der Term (q-q mod 2)/2 ist für q=2 und q=3 gleich 1,
darum habe ich ihn offenbar "im ersten Anlauf" übersehen.)

Und es làßt sich eine geschlossene "funktionale" - nicht iterative -
Lösung für alle Primzahlen (einschl. der 2) angeben und ohne bzgl.
geradem und ungeradem i unterscheiden zu müssen.


Das ist doch immernoch ein "hübsches" Ergebnis - oder!?


Wer nicht selber ràtseln will und mag, mag weiterlesen.


Die Gleichung ist eine
inhomogene lineare Differenzengleichung 1. Ordnung.
Die Lösung setzt sich aus
der "homogenen Lösung" ( A(q,i+1)= q*A(q,i) )
plus irgendeiner speziellen Lösung s
(hier zyklisch mit Periode 2)
s(i+2)=s(i), s(0)=x, s(1)=y zusammen:
A(q,i)= c*^q^i + s(i)

Damit findet man:
1) qx-y=((-1)^(i+1)+(-1)^q)*(q-q mod 2)/2
2) -x+qy=((-1)^i+(-1)^q)*(q-q mod 2)/2
und damit
(q^2-1)y=[(q-1)+(q+1)(-1)^q]*(q-q mod 2)/2
Daraus folgt:
y=...=[(-1)^q/(q-1)+1/(q+1)]*(q-q mod 2)/2
und damit
x=...=[(-1)^q/(q-1)-1/(q+1)]*(q-q mod 2)/2

Die Startwerte der Folgen sind virtuell, d.h. sie haben keine
mathematisch Entsprechung als rQR's.
Für sie gilt (invers aus A(q,1) berechnet):
A(q,0)= [( 1 +(-1)^q )/2]*(q-q mod 2)/2
.
Damit ergibt sich die allg. Lösung zu
A(q,i)= c*^q^i +x, wenn i gerade (bzw. +y, wenn i ungerade).
Damit bestimmt sich c zu
c= A(q,0) -x = ...
...=(1+(-1)^q)/2-((-1)^q/(q-1)-1/(q+1))*(q-qmod2)/2=...
...=[(q+3)/(q+1)+(q-3)/(q-1)*(-1)^q]*(q-qmod2)/4

Damit ist die allg. Lösung aber vollstàndig bestimmt!

Hübsche iterative Folge _und_
eine hübsche funktionale Lösung - oder!?

Test: Z.B. (s.o.) q=2 ==> c= 1/3, x= 2/3 und y= 4/3
A(2,i)= [ q^i +2(i mod 2) +4( i+1 mod 2) ]/3= ...
... = ( 2^i +2 bzw. +4 )/3 = 1, 2, 2, 4, 6, 12, ... für i= 0,1,...
Wegen rQR()= A()/2 +1 ==> rQR(2,i)= (1.5) 2 2 3 4 7, ...
Oder q=3 ==> c= 3/4, x= -3/4 und y= -1/4
A(3,i)= [ 3q^i -3(i mod 2) -( i+1 mod 2) ]/4= ...
... = ( 3*3^i -3 bzw. -1 )/4 = 0, 2, 6, 20, 60, ... für i= 0,1,...
Also (s.o.) rQR(3,i)= (1), 2, 4, 11, 31, ...

Da für q=1 und q=2 Gilt (q-qmod2)/2= 1 àndert sich oben nichts,
Man muß eben alles mit (q-qmod2)/2multiplizieren.

Für q=5 erhàlt man:
c=5/6, x=-5/6, y=-1/6
A(5,i)= 5/6*q^i +... ==> (0),4,20,104,520 ...
oder
#rQR(5,i)= A(5,i)/2-1 = 1,3,11,53,261,,,,

Siehe oben "Lekruj Beedassy" s=
Oder aber auch OEIS A039302.


Für mich persönlich interessant
(neben dem Spaß die Folge zu knacken!)
war dabei nur der Koeffizient c(q)
- bzw. und genauer C(q)=2/c(q) (für #rQRs).
Der Kehrwert des Grenzwert von #rQR(q,i)/q^i
(für i gegen unendlich).


Es gilt:
C(q)= 2*6/2,8/3,12/5,16/7,24/11,...; q=2,3,5,7,11,...
Und offenbar im Grenzwert q > oo
konvergiert C(q)= 2(p+1)/p * 2(1-(-1)^(q+1))
monoton (von oben) gegen 2 - leider! ;-(


Und alles (fast) just for fun! ;-)


Ein schönes Wochenende,
und sei ruhig mal ein "Eichhörnchen"
- lach mal wieder, ruhig unter trànen!
("Unterwasser" lacht man eventuell lànger ;-) )

http://www.n-tv.de/img/18/1865446/O...Lachen.jpg


Siggi N. - Harburg
 

Lesen sie die antworten

#1 Siegfried - Siggi - Neubert
06/11/2010 - 00:19 | Warnen spam
On 5 Nov., 17:00, Siegfried - Siggi - Neubert
wrote:
On 29 Okt., 17:50, Siegfried - Siggi - Neubert
wrote unter "Erfolgreicher Holzweg! ;-)  ...":



...
Bzw. für q=3:
A(3,i)= (0) 2 6 20 60 182 550 ... ; i=(0),1,2,...


...
Und nochmal Pardon, sollte heißen
A(3,i)= (0) 2 6 20 60 182 546 ... ; i=(0),1,2,...

Ach ja, und dann vergaß ich noch eine "Vereinfachung",
wobei |x|. die nàchst kleiner/gleiche natürliche Zahl:

Wobei #rQR(a,i)= 1+2*A(q,i) und es gilt für

q=2 : A(2,i)= | (2^î +4)/3 |.
q=3 : A(3,i)= | 3^(i+1) /4 |.
q=5 : A(5,i)= | 5^(i+1) /6 |.
...
q : A(q,i)= | q^(i+1) /(q+1) |. für q>2

Trennt zwar wieder q=2 und q>2, aber ist doch herrlich einfach!

Tschüß - Siggi N.

Ähnliche fragen