Eine Frage aus dem Bereich "Quadratische Nichtreste" (/"reale Quadratische Reste")

07/11/2010 - 20:20 von Siegfried - Siggi - Neubert | Report spam
Ich habe eine (bzw. 2 - s.u. -) Frage(n)
aus dem Bereich "Quadratische Nichtreste" (QNR)
- diese steht im Zusammenhang mit der Anzahl der
verschiedenen quadratischen Reste mod p^n, p Prim
( eben "reale Quadratische Reste" rQR ).

Alle Angaben hier ohne Beweis
und - aus Erfahrung klüger geworden -
nur modulo Irrtümer und Schreibfehler! ;-) .


Def.: 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:
Die Anzahl "Reale Quadratische Reste" - als Symbol #rQR.

Einen allg. Ausdruck #rQR(p,n)=f(p,n),
für p Prim und n e IN, habe ich in den Tread über
die "Anzahl der verschiedenen quadratischen Reste
mod p^n, p Prim" angegeben.


Def.: Jacobie-Symbol (a|p):
Ist p eine Primzahl,
verhàlt sich das Jacobi-Symbol
exakt wie das Legendre-Symbol.

(a|p):= 1 oder -1 oder 0 (mod p), wenn a
quadratischer Rest (QR), kein QR oder ggt(a,p)<>1 ist.

Zur vollstàndigkeit: Ist q keine Primzahl und
q= (p_1)^(n_1)*(p_2)^(n_2)*...*(p_k)^(n_k)
die Primfaktorzerlegung von q, so definiert man

(a|q)= (a|p_1)^(n_1) * ... * (a|p_k)^(k_1)


Die rQRs unterscheiden sich also ggf.
von den "mathe. QRs" (nach Jacobie)
durch mögliche Vielfache (Vf) von p.
Im weiteren zeige ich auf, wieviele das sind
(Herleitung unten):


==> #Vf(p,i+2)= (1+ p mod 2)*(p-1)/4*p^i


Aber es bleibt meine Frage:

==> Kann man die Werte dieser Vielfachen von p "einfach" bestimmen?

Möglichst àhnlich einfach,
wie man die Werte der QRs angeben kann:
Die QR(p^n) für p>2
- die (p-1)/2 * p^(n-1) Elemente der
von p^n implizierten (zyklischen!)
multiplikativen Restegruppe -
ergeben sich als von der "4" erzeugt,
also zu (4^n mod p^n); n=1,2,...,(p-1)/2*p^(n-1)

(für 2^n sind es die ungraden Zahlen kleiner 2^n !).

Weitere Erlàuterungen siehe unten!


Rückblick:________________________________________

Damit zeigt sich erneut ein erfolgreicher "Holzweg":

Vormals am On 29 Okt., 17:50,
Siegfried - Siggi - Neubert <neub...@tu-harburg.de> wrote:

Moin moin.

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



...

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:



Das stimmt so auch nicht (s.o),
aber ich fand dort schon für q=3
...


>
#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" ;-)
... für allgemeines q>2, Prim bestimmen.



Wurde von mir Nachgereicht - auch für q=2 !



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


...
_________________________________________________


Wenn man (dann) die Richtigen Ausdrücke benutz
- meine Erinnerungen liegen eben schon lang zurück,
und ich schlage dann auch nicht immer gleich nach! ;o) -,
dann kann man den Holzweg auch als Erfolgsweg beschreiten:


Man findet (z.B.) in der Literatur:

Die mult. Restegruppe modulo p^n sind zyklisch
( genau auch die zu 2*p^n und 2 und 4 ).

Und für p^n, p Prim gilt:
Die Ordnung der entsprechnden Gruppen ist (p-1)p^(n-1).

Also ist für p=2^n, n>2 die Gruppe nicht zyklisch
- es gibt 2 "Erzeugende" - z.B. "-1" und "3".

Sei q=8=2^3: M_8 ist isomorph zu IZ_2 x IZ_4 und hat 4 Elemente
M_8= {1,-1,3,-3} (oder auch {1 3 5 7})
Es gibt nur 1 QR in M_8, die "1"
und als rQR noch die "0" und die "4",
also insgesamt 3
und es gilt (wie früher gezeigt):
#rQR(2,3)=1+1/2*|(2^î +4)/3|.=1+1/2*|(8+4)/3|=3

Für p>2, p Prim, erzeugt "2" die mult. Reste-Gruppe ( M_p ).

Z.B.: q%=p^2, mit p=5==> | M_q |= 4*5 und "2" erzeugt:
2 4 8 16 7 14 3 6 12 24 23 21 17 9 18 11 22 19 13 1
Und damit erzeugt die "4" p^2*(p-1)/2 die 10 QRs:
4 16 14 6 24 21 9 11 19 1
Es fehlt das 11 Element ist "0", da die 0 kein Element von M_25,
weil gilt (wie früher gezeigt):
#rQR(5,2)=1+1/2*|5^3 /6|.=1+1/2*|125/6|.=1+/20)/2

(Ob 2p für mich auch von interesse ist,
werde ich numerisch gelegentlich ergründen! ;o) )


Sieht man sich die Folgen für verschiedene p (=3,5,7,...) einmal an,
so "sieht" man das mit #QR= (p-1)/2*p^i gilt:

#rQR(p,i+1)= (p-1)/2*p^i +#rQR(p,i-1) = ...
... = |M_p^(i+1)| + #rQR(p,i-1)
... = #QR(p,i+1) + #rQR(p,i-1)

D.h. aber, daß #rQR(p,i-1):= #Vf(q,i+1) gilt, wobei
#Vf(q,i+1) die Anzahl der Vielfachen von q (einschl. 0) ist,
die zu |M_p^(i+1)| dazukommen, um #rQR(p,i+1) zu ergeben.

Die Sonderstellung von q=2^n für n>2 führt
durch die Elementezahl - (Ordnung, |M_q^n|)
von M_q^n zu folgendem Ausdruck:

#Vf(p,i+2)= (1+ p mod 2)*(p-1)/4*p^i= |M_p^n|= #QR(p,i)


Eine weitere Frage
(über die Frage nach den konkreten Werten der Vielfachen von p hinaus)
ist die, _warum_ dieser Zusammenhang zwischen #Vf und #QR besteht?


Frohes Schaffen in der nàchste Woche.

Gruß und tschüß - Siggi N.

P.S.: Das ist inzwischen schon richtig ein Stück Arbeit geworden,
und ich würde mich freuen, wenn jemand etwas konstruktives beitragen
könnte
- oder aber auch einfach nur, ob er (mathematischen) Sinn darin sieht!?
 

Lesen sie die antworten

#1 Jutta Gut
07/11/2010 - 22:10 | Warnen spam
Hallo Siggi!

Ich würde dir sehr gerne antworten, aber ich finde deine Postings etwas
schwierig zu lesen. sie kommen mir eher wie "laut denken" vor, und ich weiß
nicht, worauf du eigentlich hinauswillst. Kannst du deine Frage vielleicht
in einem Absatz formulieren?

mfg Jutta

"Siegfried - Siggi - Neubert" schrieb im Newsbeitrag
news:

Ich habe eine (bzw. 2 - s.u. -) Frage(n)
aus dem Bereich "Quadratische Nichtreste" (QNR)
- diese steht im Zusammenhang mit der Anzahl der
verschiedenen quadratischen Reste mod p^n, p Prim
( eben "reale Quadratische Reste" rQR ).

Alle Angaben hier ohne Beweis
und - aus Erfahrung klüger geworden -
nur modulo Irrtümer und Schreibfehler! ;-) .


Def.: 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:
Die Anzahl "Reale Quadratische Reste" - als Symbol #rQR.

Einen allg. Ausdruck #rQR(p,n)=f(p,n),
für p Prim und n e IN, habe ich in den Tread über
die "Anzahl der verschiedenen quadratischen Reste
mod p^n, p Prim" angegeben.


Def.: Jacobie-Symbol (a|p):
Ist p eine Primzahl,
verhàlt sich das Jacobi-Symbol
exakt wie das Legendre-Symbol.

(a|p):= 1 oder -1 oder 0 (mod p), wenn a
quadratischer Rest (QR), kein QR oder ggt(a,p)<>1 ist.

Zur vollstàndigkeit: Ist q keine Primzahl und
q= (p_1)^(n_1)*(p_2)^(n_2)*...*(p_k)^(n_k)
die Primfaktorzerlegung von q, so definiert man

(a|q)= (a|p_1)^(n_1) * ... * (a|p_k)^(k_1)


Die rQRs unterscheiden sich also ggf.
von den "mathe. QRs" (nach Jacobie)
durch mögliche Vielfache (Vf) von p.
Im weiteren zeige ich auf, wieviele das sind
(Herleitung unten):


==> #Vf(p,i+2)= (1+ p mod 2)*(p-1)/4*p^i


Aber es bleibt meine Frage:

==> Kann man die Werte dieser Vielfachen von p "einfach" bestimmen?

Möglichst àhnlich einfach,
wie man die Werte der QRs angeben kann:
Die QR(p^n) für p>2
- die (p-1)/2 * p^(n-1) Elemente der
von p^n implizierten (zyklischen!)
multiplikativen Restegruppe -
ergeben sich als von der "4" erzeugt,
also zu (4^n mod p^n); n=1,2,...,(p-1)/2*p^(n-1)

(für 2^n sind es die ungraden Zahlen kleiner 2^n !).

Weitere Erlàuterungen siehe unten!


Rückblick:________________________________________

Damit zeigt sich erneut ein erfolgreicher "Holzweg":

Vormals am On 29 Okt., 17:50,
Siegfried - Siggi - Neubert wrote:
Moin moin.

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



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



Das stimmt so auch nicht (s.o),
aber ich fand dort schon für q=3
...

>
#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" ;-)
... für allgemeines q>2, Prim bestimmen.



Wurde von mir Nachgereicht - auch für q=2 !


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


...
_________________________________________________


Wenn man (dann) die Richtigen Ausdrücke benutz
- meine Erinnerungen liegen eben schon lang zurück,
und ich schlage dann auch nicht immer gleich nach! ;o) -,
dann kann man den Holzweg auch als Erfolgsweg beschreiten:


Man findet (z.B.) in der Literatur:

Die mult. Restegruppe modulo p^n sind zyklisch
( genau auch die zu 2*p^n und 2 und 4 ).

Und für p^n, p Prim gilt:
Die Ordnung der entsprechnden Gruppen ist (p-1)p^(n-1).

Also ist für p=2^n, n>2 die Gruppe nicht zyklisch
- es gibt 2 "Erzeugende" - z.B. "-1" und "3".

Sei q=8=2^3: M_8 ist isomorph zu IZ_2 x IZ_4 und hat 4 Elemente
M_8= {1,-1,3,-3} (oder auch {1 3 5 7})
Es gibt nur 1 QR in M_8, die "1"
und als rQR noch die "0" und die "4",
also insgesamt 3
und es gilt (wie früher gezeigt):
#rQR(2,3)=1+1/2*|(2^î +4)/3|.=1+1/2*|(8+4)/3|=3

Für p>2, p Prim, erzeugt "2" die mult. Reste-Gruppe ( M_p ).

Z.B.: q%=p^2, mit p=5==> | M_q |= 4*5 und "2" erzeugt:
2 4 8 16 7 14 3 6 12 24 23 21 17 9 18 11 22 19 13 1
Und damit erzeugt die "4" p^2*(p-1)/2 die 10 QRs:
4 16 14 6 24 21 9 11 19 1
Es fehlt das 11 Element ist "0", da die 0 kein Element von M_25,
weil gilt (wie früher gezeigt):
#rQR(5,2)=1+1/2*|5^3 /6|.=1+1/2*|125/6|.=1+/20)/2

(Ob 2p für mich auch von interesse ist,
werde ich numerisch gelegentlich ergründen! ;o) )


Sieht man sich die Folgen für verschiedene p (=3,5,7,...) einmal an,
so "sieht" man das mit #QR= (p-1)/2*p^i gilt:

#rQR(p,i+1)= (p-1)/2*p^i +#rQR(p,i-1) = ...
... = |M_p^(i+1)| + #rQR(p,i-1)
... = #QR(p,i+1) + #rQR(p,i-1)

D.h. aber, daß #rQR(p,i-1):= #Vf(q,i+1) gilt, wobei
#Vf(q,i+1) die Anzahl der Vielfachen von q (einschl. 0) ist,
die zu |M_p^(i+1)| dazukommen, um #rQR(p,i+1) zu ergeben.

Die Sonderstellung von q=2^n für n>2 führt
durch die Elementezahl - (Ordnung, |M_q^n|)
von M_q^n zu folgendem Ausdruck:

#Vf(p,i+2)= (1+ p mod 2)*(p-1)/4*p^i= |M_p^n|= #QR(p,i)


Eine weitere Frage
(über die Frage nach den konkreten Werten der Vielfachen von p hinaus)
ist die, _warum_ dieser Zusammenhang zwischen #Vf und #QR besteht?


Frohes Schaffen in der nàchste Woche.

Gruß und tschüß - Siggi N.

P.S.: Das ist inzwischen schon richtig ein Stück Arbeit geworden,
und ich würde mich freuen, wenn jemand etwas konstruktives beitragen
könnte
- oder aber auch einfach nur, ob er (mathematischen) Sinn darin sieht!?

Ähnliche fragen