Erfolgreicher Holzweg! ;-) - War: Spezielle iterative Folge

29/10/2010 - 18:50 von Siegfried - Siggi - Neubert | Report spam
Moin moin.

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


Es geht um die Anzahl der real möglichen Werte die ein Ausdruck
"x^2 mod p^n" annehmen kann (für p Primzahl und x e IN)
- sozusagen: "Reale Quadratische Reste".


Die Mathematik kennt Quadratische (Nicht-)Reste (QR) und
es gilt für p>2, Prim:

Es gibt genau #QR(p)= ((p-1)/2 QRs (Quadratische Reste)
- genausoviele wie Nichtreste.
(Allg. gilt, vielfache von p sind weder Reste noch Nichtreste!)

Sei hier p>2 angenommen.
Ich meinte mich aber (fàlschlich) zu erinnern, daß es hieß:
#QR(p^n)= p^(n-1)*(p+1)/2
Das stimmt nicht
- das ist die Ordnung der multiplikativen Gruppe IZ_p^(n) -,
aber sehen wir doch mal weiter:

Die Vielfachen von p gehören ja nicht dazu
(p^n-p)/p= p^(n-1)-1:

#rQR(p^n)= p^(n-1)*(p+1)/2 -(p^(n-1)+1)= ...
... = p^(n-1)[(p+1)/2 -1] +1= ...
... = p^(n-1)(p-1)/2 +1

Und siehe da - im Kopf überschlagen -,
es ergibt sich für
p=3: 2, 4, ...
p=5: 3, 11, ...
p=7; 4, 22, ...
wie ich es auch schon
- siehe "1/2 * "Spezielle iterative Folge" -
gefunden hatte.

Ich war ja begeistert, und begann zu überlegen warum genau daß so sei,
wobei mir dann mein Irrtum bewußt wurde und
ich prüfte genauer - in (.) die erwarteten Werte:
p=3: 2, 4, 10(11), 28(31), ...
p=5: 3, 11, 51(53), 251(261), ...
p=7; 4, 22, 148(151), 1030(1051), ...

Eventuell sieht man schnell, daß man, wenn man das vorletzte
Folgenglied-1 addiert, wieder erhàlt:
p=3: 2, 4, 11, 31, 92, 274, ...
p=5: 3, 11, 53, 261, 1303, 6511
p=7; 4, 22, 151, 1051, 7354, 51472, ...

Das ergibt (auch für die folgenden Werte) die richtigen Zahlen!???

Damit hat man (wieder) eine inhomogene lineare Differenzengleichung
- jetzt aber zweiten Grades:

für i=1,2: #rQR(q,i)= (q-1)/2*q^(i-1) +1
für i=3,...: #rQR(q,i+2)= #rQR(q,i) +q^(i-1)*(q-1)/2

hier mit der spez. Lsg.
("sieht mam" aus (q-1)/2*q^(i-1)= d*q^(i-1) )
und der homog. Lsg. b +c*(-1)^(i-1)
(als allg. Lsg. der Gl. z^2 -1= 0)

Also kurz a_i = b +c*(-1)^(i-1) +d*q^(i-1)
(woraus man b, c und d bestimmen 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.

(Müßten die Ausdrücke nicht irgendwie alle gleich sein!
Aber dazu habe ich jetzt keine Lust mehr
- genauso wenig wie für die allg. Lösung #rQR(q,i) ;-) )


Ein schönes Wochenende!

Vielleicht mag das ja tatsàchlich jemand lesen!?

Herzlichen Gruß, danke "wer mir bisher folgte" und tschüß


Siggi N. - Hamburg
 

Lesen sie die antworten

#1 Siegfried - Siggi - Neubert
30/10/2010 - 02:28 | Warnen spam
On 29 Okt., 18:50, Siegfried - Siggi - Neubert
wrote:
Moin moin.

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

Es geht um die Anzahl der real möglichen Werte die ein Ausdruck
"x^2 mod p^n" annehmen kann (für p Primzahl und x e IN)
- sozusagen: "Reale Quadratische Reste".

Die Mathematik kennt Quadratische (Nicht-)Reste (QR) und
es gilt für p>2, Prim:

Es gibt genau #QR(p)= ((p-1)/2 QRs (Quadratische Reste)
- genausoviele wie Nichtreste.
(Allg. gilt, vielfache von p sind weder Reste noch Nichtreste!)

Sei hier p>2 angenommen.
Ich meinte mich aber (fàlschlich) zu erinnern, daß es hieß:
#QR(p^n)= p^(n-1)*(p+1)/2
Das stimmt nicht
- das ist die Ordnung der multiplikativen Gruppe IZ_p^(n) -,
aber sehen wir doch mal weiter:

Die Vielfachen von p gehören ja nicht dazu
(p^n-p)/p= p^(n-1)-1:

#rQR(p^n)= p^(n-1)*(p+1)/2 -(p^(n-1)+1)= ...
... = p^(n-1)[(p+1)/2 -1] +1= ...
... = p^(n-1)(p-1)/2 +1

Und siehe da - im Kopf überschlagen -,
es ergibt sich für
p=3: 2, 4, ...
p=5: 3, 11, ...
p=7; 4, 22, ...
wie ich es auch schon
- siehe "1/2 * "Spezielle iterative Folge" -
gefunden hatte.

Ich war ja begeistert, und begann zu überlegen warum genau daß so sei,
wobei mir dann mein Irrtum bewußt wurde und
ich prüfte genauer - in (.) die erwarteten Werte:
p=3: 2, 4, 10(11), 28(31),  ...
p=5: 3, 11, 51(53), 251(261), ...
p=7; 4, 22, 148(151), 1030(1051), ...

Eventuell sieht man schnell, daß man, wenn man das vorletzte
Folgenglied-1 addiert, wieder erhàlt:
p=3: 2, 4, 11, 31,  92, 274, ...
p=5: 3, 11, 53, 261, 1303, 6511
p=7; 4, 22, 151, 1051, 7354, 51472, ...

Das ergibt (auch für die folgenden Werte) die richtigen Zahlen!???

Damit hat man (wieder) eine inhomogene lineare Differenzengleichung
- jetzt aber zweiten Grades:

für i=1,2:   #rQR(q,i)=   (q-1)/2*q^(i-1) +1
für i=3,...: #rQR(q,i+2)= #rQR(q,i) +q^(i-1)*(q-1)/2

hier mit der spez. Lsg.
("sieht mam" aus (q-1)/2*q^(i-1)= d*q^(i-1) )
und der homog. Lsg. b +c*(-1)^(i-1)
(als allg. Lsg. der Gl. z^2 -1= 0)

Also kurz a_i = b +c*(-1)^(i-1) +d*q^(i-1)
(woraus man b, c und d bestimmen kann!)

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


^^^^^^^^^^^

#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.

(Müßten die Ausdrücke nicht irgendwie alle gleich sein!
Aber dazu habe ich jetzt keine Lust mehr
- genauso wenig wie für die allg. Lösung #rQR(q,i)  ;-) )

Ein schönes Wochenende!

Vielleicht mag das ja tatsàchlich jemand lesen!?

Herzlichen Gruß, danke "wer mir bisher folgte" und tschüß

Siggi N. - Hamburg

Ähnliche fragen