Permutation für Primzahlen < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:32 So 06.01.2013 | | Autor: | rolo4 |
| Aufgabe | Für jede Primzahl p ist die Menge [mm] \IZ/p\IZ={[1],...[p]} [/mm] ein Körper, also ist für [mm] p\not=2 [/mm] die Abbildung [mm] \partial: \IZ/p\IZ \to \IZ/p\IZ [/mm] mit [x] [mm] \mapsto [/mm] [2x] bijektiv dh. [mm] \partial [/mm] ist eine Permutation
Sei p= [mm] 2^{43112609}-1 [/mm] die größte bekannte Primzahl. Berechnen Sie [mm] sign(\partial) [/mm] |
In dem vorherigen Aufgabenteil konnte ich erfolgreich das signum der Permutationen für p=5 und für p=7 berechnen. Ich habe daraufhin einfach die nächsten Primzahlen mit ihren Sigma berechnet nur finde ich leider keine Regelmäßigkeiten.
Ausrechnen sollte ja hier eher nicht Lösungsweg sein.
|
|
| |
|
Hallo rolo,
gerade natürlich. 
> Für jede Primzahl p ist die Menge [mm]\IZ/p\IZ={[1],...[p]}[/mm]
> ein Körper, also ist für [mm]p\not=2[/mm] die Abbildung [mm]\partial: \IZ/p\IZ \to \IZ/p\IZ[/mm]
> mit [x] [mm]\mapsto[/mm] [2x] bijektiv dh. [mm]\partial[/mm] ist eine
> Permutation
Steht das [mm] \partial [/mm] hier für [mm] $\delta$?
[/mm]
> Sei p= [mm]2^{43112609}-1[/mm] die größte bekannte Primzahl.
> Berechnen Sie [mm]sign(\partial)[/mm]
Wie gesagt, gerade - also "+".
> In dem vorherigen Aufgabenteil konnte ich erfolgreich das
> signum der Permutationen für p=5 und für p=7 berechnen.
> Ich habe daraufhin einfach die nächsten Primzahlen mit
> ihren Sigma berechnet nur finde ich leider keine
> Regelmäßigkeiten.
Betrachte [mm] \bruch{1}{8}(p^2-1). [/mm] Ist das gerade, ist es die Permutation auch, und umgekehrt.
> Ausrechnen sollte ja hier eher nicht Lösungsweg sein.
Wie kommt man nun darauf? Betrachten wir mal p=13.
[mm] \partial [/mm] bildet nun so ab:
[mm] $[0,1,2,3,4,5,6,7,8,9,10,11,12,13]\to[0,2,4,6,8,10,12,1,3,5,7,9,11]$
[/mm]
Wenn wir das zurückordnen wollen, dann können wir z.B. erst einmal die 1 an die richtige Stelle "schieben":
[mm] $[0,2,4,6,8,10,12,1,3,5,7,9,11]\to[0,1,2,4,6,8,10,12,3,5,7,9,11]$
[/mm]
Das erreicht man durch 6 Vertauschungen, bei allgemeinem ungeradem p durch [mm] \tfrac{1}{2}(p-1) [/mm] Vertauschungen.
Als nächstes die 3 an die richtige Stelle:
[mm] $[0,1,2,4,6,8,10,12,3,5,7,9,11]\to[0,1,2,4,6,8,10,12,3,5,7,9,11]$
[/mm]
Das sind 5 Vertauschungen. Und so weiter, bis man zuletzt
[mm] $[0,1,2,3,4,5,6,7,8,9,10,12,11]\to[0,1,2,3,4,5,6,7,8,9,10,11,12]$
[/mm]
durch eine letzte Vertauschung erhält.
Insgesamt sind also [mm] \summe_{k=1}^{\bruch{1}{2}(p-1)}k=\bruch{\bruch{1}{2}(p-1)*\left(\bruch{1}{2}(p-1)+1\right)}{2}=\bruch{\bruch{1}{2}(p-1)*\bruch{1}{2}(p+1)}{2}=\bruch{(p-1)(p+1)}{8}=\bruch{p^2-1}{8} [/mm] Vertauschungen nötig.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:33 So 06.01.2013 | | Autor: | rolo4 |
ah super danke, das hilft mir schonmal sehr viel weiter :)
Wie kommst du auf die [mm] \bruch{1}{2}(p-1), [/mm] sodass du sie dann für alle allgemeinen Primzahlen verallgemeinern kannst?
|
|
|
| |
|
Hallo nochmal,
> ah super danke, das hilft mir schonmal sehr viel weiter :)
> Wie kommst du auf die [mm]\bruch{1}{2}(p-1),[/mm] sodass du sie
> dann für alle allgemeinen Primzahlen verallgemeinern
> kannst?
Wenn Du alle Restklassen von [0] bis [p-1] durchgehst und der Abbildung unterwirfst, dann kommen erst die [mm] \tfrac{1}{2}(p+1) [/mm] geraden Restklassen und dann die [mm] \tfrac{1}{2}(p-1) [/mm] ungeraden Restklassen heraus. Betrachte also die erste auftauchende ungerade Restklasse [1] und ihren "Standort".
Grüße
reverend
|
|
|
|
