Beweis Äquivalenz < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:26 So 18.05.2008 | | Autor: | petzimuh |
| Aufgabe | Für n [mm] \in \IN [/mm] sind die beiden folgenden Bedingungen äquivalent:
(a) n [mm] \in [/mm] P
(b) [mm] X^n [/mm] - [mm] a^n \equiv [/mm] (X - [mm] a)^n [/mm] mod [mm] n\IZ[X] [/mm] für alle a [mm] \in \IZ [/mm] |
Hallo!
ICh versuche gerade diese Aufgabe zu lösen und komme irgendwie einfach nicht weiter! Bzw. weiß eigentlich gar nicht wie ich starten soll!
Wir bekamen als Tip folgenden Satz aus der Vorlesung:
Sei n [mm] \in \IN_{2}. [/mm] Dann gilt : n [mm] \in [/mm] P [mm] \gdw [/mm] n | [mm] \vektor{n \\ v} [/mm] für alle v [mm] \in [/mm] [1, n - 1].
Ich dachte ich kann statt [mm] X^n [/mm] - [mm] a^n \equiv [/mm] (X - [mm] a)^n [/mm] mod [mm] n\IZ[X] [/mm] auch schreiben
[mm] n\IZ[X] [/mm] | [mm] X^n [/mm] - [mm] a^n [/mm] - (X - [mm] a)^n
[/mm]
nur weiß ich jetzt leider absolut nicht weiter!
Vielleciht könntet ihr mir helfen?
Vielen Dank!
LG
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:49 So 18.05.2008 | | Autor: | abakus |
> Für n [mm]\in \IN[/mm] sind die beiden folgenden Bedingungen
> äquivalent:
> (a) n [mm]\in[/mm] P
> (b) [mm]X^n[/mm] - [mm]a^n \equiv[/mm] (X - [mm]a)^n[/mm] mod [mm]n\IZ[X][/mm] für alle a [mm]\in \IZ[/mm]
>
> Hallo!
>
> ICh versuche gerade diese Aufgabe zu lösen und komme
> irgendwie einfach nicht weiter! Bzw. weiß eigentlich gar
> nicht wie ich starten soll!
>
> Wir bekamen als Tip folgenden Satz aus der Vorlesung:
> Sei n [mm]\in \IN_{2}.[/mm] Dann gilt : n [mm]\in[/mm] P [mm]\gdw[/mm] n | [mm]\vektor{n \\ v}[/mm]
> für alle v [mm]\in[/mm] [1, n - 1].
>
>
> Ich dachte ich kann statt [mm]X^n[/mm] - [mm]a^n \equiv[/mm] (X - [mm]a)^n[/mm] mod
> [mm]n\IZ[X][/mm] auch schreiben
> [mm]n\IZ[X][/mm] | [mm]X^n[/mm] - [mm]a^n[/mm] - (X - [mm]a)^n[/mm]
>
> nur weiß ich jetzt leider absolut nicht weiter!
> Vielleciht könntet ihr mir helfen?
>
> Vielen Dank!
> LG
>
Hallo,
es ist nur so eine Idee: müsste man hier nicht irgendwie mit dem kleinen Satz von Fermat weiterkommen?
Viele Grüße
Abakus
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:31 So 18.05.2008 | | Autor: | felixf |
Hallo!
> Für n [mm]\in \IN[/mm] sind die beiden folgenden Bedingungen
> äquivalent:
> (a) n [mm]\in[/mm] P
> (b) [mm]X^n[/mm] - [mm]a^n \equiv[/mm] (X - [mm]a)^n[/mm] mod [mm]n\IZ[X][/mm] für alle a [mm]\in \IZ[/mm]
>
> Hallo!
>
> ICh versuche gerade diese Aufgabe zu lösen und komme
> irgendwie einfach nicht weiter! Bzw. weiß eigentlich gar
> nicht wie ich starten soll!
>
> Wir bekamen als Tip folgenden Satz aus der Vorlesung:
> Sei n [mm]\in \IN_{2}.[/mm] Dann gilt : n [mm]\in[/mm] P [mm]\gdw[/mm] n | [mm]\vektor{n \\ v}[/mm]
> für alle v [mm]\in[/mm] [1, n - 1].
Da hast du doch schon die wichtigste Zutat. Die Richtung $(a) [mm] \Rightarrow [/mm] (b)$ bekommst du damit schnell hin; Stichwort: binomischer Lehrsatz.
Fuer die Rueckrichtung waehle doch mal $a = -1$, also rechne $(X - [mm] 1)^n$ [/mm] modulo $n [mm] \IZ[X]$ [/mm] aus. Faellt dir was auf?
> Ich dachte ich kann statt [mm]X^n[/mm] - [mm]a^n \equiv[/mm] (X - [mm]a)^n[/mm] mod
> [mm]n\IZ[X][/mm] auch schreiben
> [mm]n\IZ[X][/mm] | [mm]X^n[/mm] - [mm]a^n[/mm] - (X - [mm]a)^n[/mm]
Ja, kannst du. Es ist aequivalent dazu, dass jeder Koeffizient von [mm] $X^n [/mm] - [mm] a^n [/mm] - (X - [mm] a)^n$ [/mm] durch $n$ teilbar ist.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:12 Mo 19.05.2008 | | Autor: | petzimuh |
Hallo!
Danke für eure Antworten!!
Also ich bin da mal so vorgegangen:
erste Richtung:
[mm] "\Rightarrow" [/mm] Sei n [mm] \in [/mm] P
daraus folgt: n | [mm] \vektor{n \\ v} [/mm] , für alle v [mm] \in [/mm] [1, n-1]
d.h. [mm] \vektor{n \\ v}*x [/mm] = 0 für alle v [mm] \in [/mm] [1, n-1] und x [mm] \in \IZ
[/mm]
[mm] \Rightarrow (X-a)^{n} [/mm] = [mm] \summe_{v=1}^{n} (-1)^v \vektor{n \\ v} X^{n-v}a^{v} [/mm] = [mm] (-1)^{n}X^{n} [/mm] + [mm] (-1)^{n}a^{n} [/mm] = [mm] -X^{n}-a^{n} [/mm] da n prim
Jetzt habe das oben eben umgeformt
$ [mm] n\IZ[X] [/mm] $ | $ [mm] X^n [/mm] $ - $ [mm] a^n [/mm] $ - (X - $ [mm] a)^n [/mm] $ = $ [mm] X^n [/mm] $ - $ [mm] a^n [/mm] $ - (-$ [mm] X^n [/mm] $ - $ [mm] a^n [/mm] $) = [mm] 2X^{n}
[/mm]
stimmt das so?
Ich glaub ich bin da schon völlig durcheinander gekommen mit der Reihenfolge! Bzw. mit den Richtungen! das mit dem $ [mm] n\IZ[X] [/mm] $ verwirrt mich so.
Danke für eure Hilfe!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:16 Mo 19.05.2008 | | Autor: | petzimuh |
Hallo!
So also ich habe bei meiner obigen Überlegung einen Fehler entdeckt! Also ich hab mir das jetzt nochmals durchgedacht:
[mm] (a)\Rightarrow(b) [/mm] :
Sei n [mm] \in [/mm] P: [mm] (X-a)^{n} [/mm] = [mm] \summe_{k=0}^{n}\vektor{n \\ k}X^{n-k}(-a)^{k} \equiv X^{n}+(-a)^{n} [/mm] mod [mm] n\IZ[X] [/mm] da n | [mm] \vektor{n \\ k} [/mm] für alle
[mm] k\in [/mm] [1; n-1]
[mm] (X-a)^{n} \equiv X^{n}-a^{n} [/mm] mod [mm] n\IZ[X] [/mm] (da n prim)
Hier ist jetzt nur meine Überlegung: Was ist wenn n=2 ist? Weil dann passt das ja nicht mehr so! Ist doch auch prim...muss ich da eine Fallunterscheidung machen? Wie sieht das dann aus?
[mm] (b)\Rightarrow(a) [/mm] :
[mm] (X-a)^{n} \equiv X^{n}-a^{n} [/mm] mod [mm] n\IZ[X]
[/mm]
d.h. [mm] \summe_{k=0}^{n}\vektor{n \\ k}X^{n-k}(-a)^{k} [/mm] - [mm] (X^{n}-a^{n}) \equiv [/mm] 0 mod [mm] n\IZ[X]
[/mm]
jetzt hebe ich [mm] X^{n}+(-a)^{n} [/mm] heraus bzw. schreibe um:
[mm] X^{n} [/mm] + [mm] (-a)^{n} [/mm] + [mm] \summe_{k=1}^{n-1}\vektor{n \\ k} X^{n-k}(-a)^{k} -X^{n} [/mm] + [mm] a^{n} \equiv [/mm] 0 mod [mm] n\IZ[X]
[/mm]
Dann ergibt dies:
(aber wieder nur wenn n [mm] \not= [/mm] 2 ....weil sonst würde es nicht wegfallen. Sollte ich hier wieder eine Fallunterscheidung machen? Wenn ja, wie?)
[mm] \summe_{k=1}^{n-1}\vektor{n \\ k} X^{n-k}(-a)^{k} \equiv [/mm] 0 mod [mm] n\IZ[X]
[/mm]
und dies ist erfüllt wenn n | [mm] \vektor{n \\ k} \gdw [/mm] n [mm] \in [/mm] P
Stimmt das so?
Vielleicht könntet ihr mir ja noch helfen wegen dem obigen...wenn n=2 wäre!
Dankeschön!
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:35 Mo 19.05.2008 | | Autor: | felixf |
Hallo
> So also ich habe bei meiner obigen Überlegung einen Fehler
> entdeckt! Also ich hab mir das jetzt nochmals
> durchgedacht:
>
> [mm](a)\Rightarrow(b)[/mm] :
>
> Sei n [mm]\in[/mm] P: [mm](X-a)^{n}[/mm] = [mm]\summe_{k=0}^{n}\vektor{n \\ k}X^{n-k}(-a)^{k} \equiv X^{n}+(-a)^{n}[/mm]
> mod [mm]n\IZ[X][/mm] da n | [mm]\vektor{n \\ k}[/mm] für alle
> [mm]k\in[/mm] [1; n-1]
> [mm](X-a)^{n} \equiv X^{n}-a^{n}[/mm] mod [mm]n\IZ[X][/mm] (da n prim)
Genau, soweit ok.
> Hier ist jetzt nur meine Überlegung: Was ist wenn n=2 ist?
In dem fall ist $-1 [mm] \equiv [/mm] 1 [mm] \pmod{n}$, [/mm] womit [mm] $(-1)^n \equiv 1^n \equiv [/mm] 1 [mm] \equiv [/mm] -1 [mm] \pmod{n}$ [/mm] ist.
> [mm](b)\Rightarrow(a)[/mm] :
>
> [mm](X-a)^{n} \equiv X^{n}-a^{n}[/mm] mod [mm]n\IZ[X][/mm]
>
> d.h. [mm]\summe_{k=0}^{n}\vektor{n \\ k}X^{n-k}(-a)^{k}[/mm] -
> [mm](X^{n}-a^{n}) \equiv[/mm] 0 mod [mm]n\IZ[X][/mm]
>
> jetzt hebe ich [mm]X^{n}+(-a)^{n}[/mm] heraus bzw. schreibe um:
>
> [mm]X^{n}[/mm] + [mm](-a)^{n}[/mm] + [mm]\summe_{k=1}^{n-1}\vektor{n \\ k} X^{n-k}(-a)^{k} -X^{n}[/mm]
> + [mm]a^{n} \equiv[/mm] 0 mod [mm]n\IZ[X][/mm]
>
> Dann ergibt dies:
> (aber wieder nur wenn n [mm]\not=[/mm] 2 ....weil sonst würde es
> nicht wegfallen. Sollte ich hier wieder eine
> Fallunterscheidung machen? Wenn ja, wie?)
Gleiches Argument wie oben.
> [mm]\summe_{k=1}^{n-1}\vektor{n \\ k} X^{n-k}(-a)^{k} \equiv[/mm] 0
> mod [mm]n\IZ[X][/mm]
Das ist erstmal erfuellt, wenn $n [mm] \mid \binom{n}{k} a^k$ [/mm] fuer alle $k [mm] \in \{ 1, \dots, n-1 \}$ [/mm] gilt. (Den Faktor [mm] $(-1)^k$ [/mm] kann man weglassen.)
> und dies ist erfüllt wenn n | [mm][mm] \vektor{n \\ k}$
[/mm]
Das musst du noch zeigen. (Wie schon gesagt, waehle $a$ passend!)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:47 Mi 21.05.2008 | | Autor: | petzimuh |
Hallo!
Dankeschön für deine Hilfe!
Habs jetzt denke ich endlich geschafft!
Wenn ich a=1 wähle, dann folgt ja schon n | [mm] \vektor{n \\ k} [/mm] und hier wissen wir ja dann, dass n [mm] \in [/mm] P ist!
Bin zuerst total auf der Leitung gestanden!
Danke nochmal!! :)
LG Petra
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:09 Mi 21.05.2008 | | Autor: | felixf |
Hallo Petra,
> Dankeschön für deine Hilfe!
>
> Habs jetzt denke ich endlich geschafft!
bitte! Und schoen :)
> Wenn ich a=1 wähle, dann folgt ja schon n | [mm]\vektor{n \\ k}[/mm]
> und hier wissen wir ja dann, dass n [mm]\in[/mm] P ist!
Genau 
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:04 Mo 19.05.2008 | | Autor: | felixf |
Hallo!
> Danke für eure Antworten!!
>
> Also ich bin da mal so vorgegangen:
>
> erste Richtung:
> [mm]"\Rightarrow"[/mm] Sei n [mm]\in[/mm] P
>
> daraus folgt: n | [mm]\vektor{n \\ v}[/mm] , für alle v [mm]\in[/mm] [1,
> n-1]
>
> d.h. [mm]\vektor{n \\ v}*x[/mm] = 0 für alle v [mm]\in[/mm] [1, n-1] und x
> [mm]\in \IZ[/mm]
>
> [mm]\Rightarrow (X-a)^{n}[/mm] = [mm]\summe_{v=1}^{n} (-1)^v \vektor{n \\ v} X^{n-v}a^{v}[/mm]
> = [mm](-1)^{n}X^{n}[/mm] + [mm](-1)^{n}a^{n}[/mm] = [mm]-X^{n}-a^{n}[/mm] da n prim
Vorsicht: einmal muss die Summe bei $v = 0$ anfangen. Und dann bleibt [mm] $(-1)^0 X^n [/mm] + [mm] (-1)^n a^n$ [/mm] ueber, also [mm] $X^n [/mm] - [mm] a^n$.
[/mm]
LG Felix
|
|
|
|
