Polynom mod m < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 02:28 Fr 30.03.2007 | | Autor: | euklid |
| Aufgabe | | Zeige: Ist [mm] 1 |
Hallo, ich kann mit der Aufgabenstellung absolut nichts anfangen, da es hier auf Polynom hingewiesen wird. Weiß nicht genau, ob es um allgemeines "Polynom" geht oder evtl. bezieht sich die Aufgabe auf vorherige Aufgabe. Dabei hieß es: das Polynom f(x) = [mm] x^{\phi(q)\} [/mm] mod q nimmt die Werte 0 und 1 an, für [mm] q=p^e [/mm] mit [mm] e\in\IN [/mm] und p ist prim.
Zu dieser Aufgabe habe ich zwei Fälle unterschieden. Zum einen [mm] x^{\phi(q)\} \equiv [/mm] 0 mod q falls p Teiler von x. Zum anderen: falls p Nichtteiler von x dann: [mm] x^{\phi(q)\} \equiv [/mm] 1 mod q. Das stimmt nach Euler (siehe kleiner fermatscher Satz) da ggt (x, q) = 1
Bei jetziger Aufgabe müssen wir zeigen, dass falls [mm] 1
freundlichen Gruß
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:07 Fr 30.03.2007 | | Autor: | felixf |
Hallo!
> Zeige: Ist [mm]1
> die Werte 0 und 1 modulo m an, so ist m eine Primpotenz.
> Hallo, ich kann mit der Aufgabenstellung absolut nichts
> anfangen, da es hier auf Polynom hingewiesen wird. Weiß
> nicht genau, ob es um allgemeines "Polynom" geht oder evtl.
> bezieht sich die Aufgabe auf vorherige Aufgabe. Dabei hieß
> es: das Polynom f(x) = [mm]x^{\phi(q)\}[/mm] mod q nimmt die Werte
> 0 und 1 an, für [mm]q=p^e[/mm] mit [mm]e\in\IN[/mm] und p ist prim.
Ich wuerde sagen, das es sich auf diese Aufgabe bezieht! Also dass das gleiche $f$ gemeint ist.
> Zu dieser Aufgabe habe ich zwei Fälle unterschieden. Zum
> einen [mm]x^{\phi(q)\} \equiv[/mm] 0 mod q falls p Teiler von x.
> Zum anderen: falls p Nichtteiler von x dann: [mm]x^{\phi(q)\} \equiv[/mm]
> 1 mod q. Das stimmt nach Euler (siehe kleiner fermatscher
> Satz) da ggt (x, q) = 1
Genau.
> Bei jetziger Aufgabe müssen wir zeigen, dass falls
> [mm]1
> ist, dann ist m eine Primpotenz. Könnt Ihr mir helfen
> diese zu lösen. Wäre sehr dankbar
Ich wuerde es so anpacken: Wenn $m$ keine Primzahlpotenz ist, also wenn $m$ mindestens zwei verschiedene Primfaktoren $p$ und $p'$ hat, dann musst du einen Wert $x [mm] \in \IZ$ [/mm] konstruieren so, dass [mm] $x^{\phi(m)} \not\equiv [/mm] 0, 1 [mm] \pmod{m}$ [/mm] ist.
Dafuer kannst du wie folgt vorgehen: Finde zuerst ein [mm] $x_1$ [/mm] mit [mm] $x^{\phi(m)} \equiv [/mm] 1 [mm] \pmod{p}$ [/mm] und ein [mm] $x_2$ [/mm] mit [mm] $x^{\phi(m)} \equiv [/mm] 0 [mm] \pmod{p'}$. [/mm] Und dann benutze den Chinesischen Restsatz, um ein $x' [mm] \in \IZ$ [/mm] zu finden mit $x' [mm] \equiv x_1 \pmod{p}$ [/mm] und $x' [mm] \equiv x_2 \pmod{p'}$. [/mm] Dieses $x$ tut es dann.
LG Felix
|
|
|
|
