Selbstabbildung modn < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Es gelte [mm] x^{e} \equiv [/mm] x (modn). Sei n = pq (p und q sind Primzahlen) und p = e = 3. Rechnen Sie aus, für wie viele x in Z/nZ [mm] x^{e} \equiv [/mm] x (modn) erfüllt ist. |
Ich habe diese Frage in keinem anderen Internetforum gestellt.
Hallo,
ich komme mit dieser Aufgabe nicht zurecht. Also es soll gelten [mm] x^{3} \equiv [/mm] x (modn) = [mm] x^{3} \equiv [/mm] x (mod3q). Als ich das sah, habe ich an den chinesischen Restsatz gedacht, da 3 und q ja Primzahlen sind.
[Zwischenfrage: Kann man dann einfach schreiben:
[mm] x_{3} \equiv [/mm] x (mod3q) <->
[mm] x_{3} \equiv [/mm] x (mod3)
[mm] x_{3} \equiv [/mm] x (modq)]
Da nun [mm] x_{3} \equiv [/mm] x (mod3) für alle x in Z/3Z gilt, hätte ich schon mal drei Elemente. Aber dann weiß ich nicht weiter bzw. ich weiß nicht mal, ob das überhaupt der richtige Ansatz ist. Kann mir vielleicht jemand auf die Sprünge helfen.
Vielen Dank
Steffen
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:04 Fr 11.05.2007 | | Autor: | MicMuc |
Chinesischer Restsatz hört sich sehr gut an.
Ich persönlich würde das Ganze "elementar" lösen (ist aber nicht so schön):
[mm] $x^3-x=x(x-1)(x+1)$
[/mm]
triviale Lösungen in [mm] $Z_{3q}$: [/mm] 0, 1, 3q-1
In [mm] $Z_{3q}$ [/mm] gibt es nicht so viele Nullteiler:
die Vielfachen von 0,3,6 usw.
die Vielfachen von q: 0, q, 2q
Wählst Du eine beliebige Zahl x aus [mm] $Z_{3q}$, [/mm] so ist einer der Faktoren x, (x-1) bzw. x+1 stets ein Vielfaches von 3.
Es interessieren uns also nur die Zahlen x mit
1) q teilt x ,oder
2) q teilt x-1 ,oder
3) q teilt x+1
Die kann man noch hinschreiben.
Zu 1)
x= 0 (hatten wir schon), x=q oder x= 2q
Zu 2)
x= 1 (hatten wir schon), x=q+1 oder x= 2q+1
usw.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:17 Fr 11.05.2007 | | Autor: | felixf |
Hallo Steffen!
> Es gelte [mm]x^{e} \equiv[/mm] x (modn). Sei n = pq (p und q sind
> Primzahlen) und p = e = 3. Rechnen Sie aus, für wie viele x
> in Z/nZ [mm]x^{e} \equiv[/mm] x (modn) erfüllt ist.
> Ich habe diese Frage in keinem anderen Internetforum
> gestellt.
>
> Hallo,
>
> ich komme mit dieser Aufgabe nicht zurecht. Also es soll
> gelten [mm]x^{3} \equiv[/mm] x (modn) = [mm]x^{3} \equiv[/mm] x (mod3q). Als
> ich das sah, habe ich an den chinesischen Restsatz gedacht,
> da 3 und q ja Primzahlen sind.
>
> [Zwischenfrage: Kann man dann einfach schreiben:
>
> [mm]x_{3} \equiv[/mm] x (mod3q) <->
> [mm]x_{3} \equiv[/mm] x (mod3)
> [mm]x_{3} \equiv[/mm] x (modq)]
>
> Da nun [mm]x_{3} \equiv[/mm] x (mod3) für alle x in Z/3Z gilt, hätte
> ich schon mal drei Elemente.
Nicht ganz: wenn du die Anzahl der $x [mm] \in \IZ/q\IZ$ [/mm] mit [mm] $x^3 [/mm] = x$ kennst, und diese Anzahl $n$ ist, dann ist die Anzahl der $x [mm] \in \IZ/3q\IZ$ [/mm] mit [mm] $x^3 [/mm] = x$ gerade $3 n$.
> Aber dann weiß ich nicht weiter bzw. ich weiß nicht mal, ob das überhaupt der
> richtige Ansatz ist. Kann mir vielleicht jemand auf die Sprünge helfen.
Jetzt schau dir $x (x - 1) (x + 1) = [mm] x^3 [/mm] - x = 0$ mal in [mm] $\IZ/q\IZ$ [/mm] an. Ist $q = 2$, so gibt es zwei Loesungen (naemlich alle Elemente, da dort $1 = -1$ ist), und ist $q > 2$, so gibt es drei Loesungen (da dort $1 [mm] \neq [/mm] -1$ ist).
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:42 Fr 11.05.2007 | | Autor: | steffenhst |
Vielen Dank euch beiden. Grüße, Steffen
|
|
|
|
