Abbildung endlicher Körper < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:12 So 06.05.2012 | | Autor: | teo |
| Aufgabe | | Sei K ein endlicher Körper mit q Elementen und sei [mm] f: K \to K [/mm] eine Abbildung. Zeigen Sie, dass es ein Polynom p [mm] \in [/mm] K[x] gibt mit p(a) = f(a) für alle a [mm] \in [/mm] K, und beweisen Sie, dass das Polynom p eindeutig bestimmt ist, wenn man zusätzlich grad(p) < q fordert. |
Hallo,
ich weiß wieder einmal nicht, wie man an diese Aufgabe herangeht. Wäre für Hinweise sehr dankbar!
Viele Grüße
teo
|
|
| |
|
moin teo,
Nimm hier einfach mal an ein solches Polynom existiert. Dann hat es die Form $p(x) = [mm] a_n*x^n [/mm] + [mm] \ldots [/mm] + [mm] a_1*x [/mm] + [mm] a_0$ [/mm] für ein $n [mm] \in \IN$ [/mm] und die [mm] $a_i \in [/mm] K$ beliebig.
Setzt du nun $x$ und $f(x)$ ein so erhälst du ein lineares Gleichungssystem mit den Unbekannten [mm] $a_0$ [/mm] bis [mm] $a_n$ [/mm] und du sollst sagen, dass dieses lösbar ist; für $n<q$ sogar eindeutig.
Für LGS kennst du sicher schon einige Verfahren zur Lösung, überlege dir also in Ruhe wie du an dieses hier herangehst.
Als Tipp: Du kannst (nicht zwingend, nur wenn du möchtest) hier den Gaußalgorithmus verwenden, denn dieser funktioniert über jedem beliebigen Körper.
lg
Schadow
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:45 So 06.05.2012 | | Autor: | teo |
> moin teo,
hallo danke für die antwort!
>
> Nimm hier einfach mal an ein solches Polynom existiert.
> Dann hat es die Form [mm]p(x) = a_n*x^n + \ldots + a_1*x + a_0[/mm]
> für ein [mm]n \in \IN[/mm] und die [mm]a_i \in K[/mm] beliebig.
> Setzt du nun [mm]x[/mm] und [mm]f(x)[/mm] ein so erhälst du ein lineares
> Gleichungssystem mit den Unbekannten [mm]a_0[/mm] bis [mm]a_n[/mm] und du
Ich seh gerade noch nicht wie das LGS aussehen soll. Wie soll ich x und f(x) einsetzen?
> sollst sagen, dass dieses lösbar ist; für [mm]n
> eindeutig.
> Für LGS kennst du sicher schon einige Verfahren zur
> Lösung, überlege dir also in Ruhe wie du an dieses hier
> herangehst.
das sollte ich dann hinkriegen..
> Als Tipp: Du kannst (nicht zwingend, nur wenn du
> möchtest) hier den Gaußalgorithmus verwenden, denn dieser
> funktioniert über jedem beliebigen Körper.
>
> lg
>
> Schadow
danke!
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:51 Mo 21.05.2012 | | Autor: | felixf |
Moin
> > Nimm hier einfach mal an ein solches Polynom existiert.
> > Dann hat es die Form [mm]p(x) = a_n*x^n + \ldots + a_1*x + a_0[/mm]
> > für ein [mm]n \in \IN[/mm] und die [mm]a_i \in K[/mm] beliebig.
> > Setzt du nun [mm]x[/mm] und [mm]f(x)[/mm] ein so erhälst du ein lineares
> > Gleichungssystem mit den Unbekannten [mm]a_0[/mm] bis [mm]a_n[/mm] und du
>
> Ich seh gerade noch nicht wie das LGS aussehen soll. Wie
> soll ich x und f(x) einsetzen?
Nun, in der Schule hast du doch schon sicher mal Aufgaben geloest wie "Finde ein Polynom von Grad 2, welches in $x = 1$ den Wert 2 und in $x = 3$ den Wert 5 und in $x = 4$ den Wert 23 annimmt." Das hast du damals ueber ein lineares Gleichungssystem gemacht. Wenn du dich dran erinnerst, wie das geht, solltest du hier auch kein Problem mehr haben.
> > sollst sagen, dass dieses lösbar ist; für [mm]n
> > eindeutig.
> > Für LGS kennst du sicher schon einige Verfahren zur
> > Lösung, überlege dir also in Ruhe wie du an dieses hier
> > herangehst.
>
> das sollte ich dann hinkriegen..
Wenn du die Aufgabe so loesen willst, brauchst du einen speziellen Trick, damit es klappt. Der andere Ansatz via Lagrange-Interpolation und Polynomdivision ist da besser.
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:52 So 06.05.2012 | | Autor: | tobit09 |
Hallo teo,
sei [mm] $K=\{a_1,\ldots,a_q\}$.
[/mm]
Zur Existenz:
Bastel dir mal für $i=1,...,q$ Polynome [mm] $p_i$ [/mm] mit [mm] $p_i(a_i)=f(a_i)$ [/mm] und [mm] $p_i(a_j)=0$ [/mm] für [mm] $j\not=i$. [/mm] Letzteres ist gleichbedeutend damit, dass [mm] $p_i$ [/mm] Vielfaches von [mm] $(X-a_j)$ [/mm] ist.
Dann leistet [mm] $p:=\sum_{i=1}^qp_i$ [/mm] das Gewünschte.
Zur Eindeutigkeit:
Seien [mm] $p_1,p_2$ [/mm] Polynome vom Grad <q mit [mm] $p_1(a_i)=p_2(a_i)=f(a_i)$ [/mm] für alle [mm] $i=1,\ldots,n$.
[/mm]
Zu zeigen ist [mm] $p_1-p_2=0$.
[/mm]
Wir wissen, dass für alle [mm] $i=1,\ldots,n$ [/mm] gilt [mm] $p_1-p_2(a_i)=f(a_i)-f(a_i)=0$. [/mm] Also ist [mm] $p_1-p_2$ [/mm] Vielfaches von [mm] $(X-a_i)$.
[/mm]
Kommst du damit weiter?
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:05 So 06.05.2012 | | Autor: | teo |
> Hallo teo,
>
Hallo, danke für die antwort.
> sei [mm]K=\{a_1,\ldots,a_q\}[/mm].
>
>
> Zur Existenz:
>
> Bastel dir mal für [mm]i=1,...,q[/mm] Polynome [mm]p_i[/mm] mit
> [mm]p_i(a_i)=f(a_i)[/mm] und [mm]p_i(a_j)=0[/mm] für [mm]j\not=i[/mm]. Letzteres ist
> gleichbedeutend damit, dass [mm]p_i[/mm] Vielfaches von [mm](X-a_j)[/mm]
> ist.
Sehen dann die [mm] p_{i}s [/mm] so aus:
[mm] p_{1} = (x-a_{2})(x-a_{3})***(x-a_{q}) [/mm]
[mm] p_{2} = (x-a_{1})(x-a_{3})***(x-a_{q}) [/mm]
[mm] ... [/mm]
[mm] p_{i} = (x-a_{1})(x-a_{2})***(x-a_{i-1})(x-a_{i+1})***(x-a_{q}) [/mm]
[mm] ... [/mm]
[mm] p_{q}=(x-a_{1})***(x-a_{q-1}) [/mm]
Aber dann ist der Grad von p ja immer kleiner als q. Oder bau ich an die [mm] p_{i}s [/mm] noch was beliebiges an?
>
> Dann leistet [mm]p:=\sum_{i=1}^qp_i[/mm] das Gewünschte.
>
>
> Zur Eindeutigkeit:
>
> Seien [mm]p_1,p_2[/mm] Polynome vom Grad <q mit
> [mm]p_1(a_i)=p_2(a_i)=f(a_i)[/mm] für alle [mm]i=1,\ldots,n[/mm].
>
> Zu zeigen ist [mm]p_1-p_2=0[/mm].
>
> Wir wissen, dass für alle [mm]i=1,\ldots,n[/mm] gilt
> [mm]p_1-p_2(a_i)=f(a_i)-f(a_i)=0[/mm]. Also ist [mm]p_1-p_2[/mm] Vielfaches
> von [mm](X-a_i)[/mm]
Wo genau kommt jetzt hier ins Spiel das grad(p) < q ist?
>
> Kommst du damit weiter?
So halb 
>
> Viele Grüße
> Tobias
Viele Grüße!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:09 So 06.05.2012 | | Autor: | tobit09 |
> > Zur Existenz:
> >
> > Bastel dir mal für [mm]i=1,...,q[/mm] Polynome [mm]p_i[/mm] mit
> > [mm]p_i(a_i)=f(a_i)[/mm] und [mm]p_i(a_j)=0[/mm] für [mm]j\not=i[/mm]. Letzteres ist
> > gleichbedeutend damit, dass [mm]p_i[/mm] Vielfaches von [mm](X-a_j)[/mm]
> > ist.
>
> Sehen dann die [mm]p_{i}s[/mm] so aus:
>
> [mm]p_{1} = (x-a_{2})(x-a_{3})***(x-a_{q})[/mm]
> [mm]p_{2} = (x-a_{1})(x-a_{3})***(x-a_{q})[/mm]
>
> [mm]...[/mm]
> [mm]p_{i} = (x-a_{1})(x-a_{2})***(x-a_{i-1})(x-a_{i+1})***(x-a_{q})[/mm]
>
> [mm]...[/mm]
> [mm]p_{q}=(x-a_{1})***(x-a_{q-1})[/mm]
Fast. Diese [mm] $p_i$ [/mm] haben schonmal genau die [mm] $a_j$ [/mm] für [mm] $j\not=i$ [/mm] als Nullstellen. Multipliziere jetzt noch jeweils mit einem geeigneten Vorfaktor, damit [mm] $p_i(a_i)=f(a_i)$ [/mm] gilt.
> Aber dann ist der Grad von p ja immer kleiner als q.
Das ist ja sogar vorteilhaft. Dann haben wir gleich mitbewiesen, dass es ein solches Polynom p vom Grad <q gibt.
> > Zur Eindeutigkeit:
> >
> > Seien [mm]p_1,p_2[/mm] Polynome vom Grad <q mit
> > [mm]p_1(a_i)=p_2(a_i)=f(a_i)[/mm] für alle [mm]i=1,\ldots,n[/mm].
> >
> > Zu zeigen ist [mm]p_1-p_2=0[/mm].
> >
> > Wir wissen, dass für alle [mm]i=1,\ldots,n[/mm] gilt
> > [mm]p_1-p_2(a_i)=f(a_i)-f(a_i)=0[/mm]. Also ist [mm]p_1-p_2[/mm] Vielfaches
> > von [mm](X-a_i)[/mm]
>
> Wo genau kommt jetzt hier ins Spiel das grad(p) < q ist?
[mm] $p_1-p_2$ [/mm] ist Vielfaches von [mm] $(X-a_i)$ [/mm] für alle [mm] $i=1,\ldots,n$. [/mm] Also hat dieses Polynom die Gestalt
[mm] $p_1-p_2=(X-a_1)*(X-a_2)*\ldots*(X-a_q)*g$
[/mm]
für ein Polynom g. Stelle nun Gradbetrachtungen an, um zu zeigen, dass $g=0$ sein muss. Insbesondere ist damit wie gewünscht [mm] $p_1-p_2=0$.
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:26 So 06.05.2012 | | Autor: | teo |
> > > Zur Existenz:
> > >
> > > Bastel dir mal für [mm]i=1,...,q[/mm] Polynome [mm]p_i[/mm] mit
> > > [mm]p_i(a_i)=f(a_i)[/mm] und [mm]p_i(a_j)=0[/mm] für [mm]j\not=i[/mm]. Letzteres ist
> > > gleichbedeutend damit, dass [mm]p_i[/mm] Vielfaches von [mm](X-a_j)[/mm]
> > > ist.
> >
> > Sehen dann die [mm]p_{i}s[/mm] so aus:
> >
> > [mm]p_{1} = (x-a_{2})(x-a_{3})***(x-a_{q})[/mm]
> > [mm]p_{2} = (x-a_{1})(x-a_{3})***(x-a_{q})[/mm]
>
> >
> > [mm]...[/mm]
> > [mm]p_{i} = (x-a_{1})(x-a_{2})***(x-a_{i-1})(x-a_{i+1})***(x-a_{q})[/mm]
>
> >
> > [mm]...[/mm]
> > [mm]p_{q}=(x-a_{1})***(x-a_{q-1})[/mm]
> Fast. Diese [mm]p_i[/mm] haben schonmal genau die [mm]a_j[/mm] für [mm]j\not=i[/mm]
> als Nullstellen. Multipliziere jetzt noch jeweils mit einem
> geeigneten Vorfaktor, damit [mm]p_i(a_i)=f(a_i)[/mm] gilt.
D.h. ich multipliziere einfach jeweils noch mit einem Polynom [mm] g_{i}?
[/mm]
> > Aber dann ist der Grad von p ja immer kleiner als q.
> Das ist ja sogar vorteilhaft. Dann haben wir gleich
> mitbewiesen, dass es ein solches Polynom p vom Grad <q
> gibt.
>
>
> > > Zur Eindeutigkeit:
> > >
> > > Seien [mm]p_1,p_2[/mm] Polynome vom Grad <q mit
> > > [mm]p_1(a_i)=p_2(a_i)=f(a_i)[/mm] für alle [mm]i=1,\ldots,n[/mm].
> > >
> > > Zu zeigen ist [mm]p_1-p_2=0[/mm].
> > >
> > > Wir wissen, dass für alle [mm]i=1,\ldots,n[/mm] gilt
> > > [mm]p_1-p_2(a_i)=f(a_i)-f(a_i)=0[/mm]. Also ist [mm]p_1-p_2[/mm] Vielfaches
> > > von [mm](X-a_i)[/mm]
> >
Weil [mm] (X-a_{i}) [/mm] = 0 für [mm] x=a_{i}?
[/mm]
> > Wo genau kommt jetzt hier ins Spiel das grad(p) < q ist?
> [mm]p_1-p_2[/mm] ist Vielfaches von [mm](X-a_i)[/mm] für alle [mm]i=1,\ldots,n[/mm].
> Also hat dieses Polynom die Gestalt
>
> [mm]p_1-p_2=(X-a_1)*(X-a_2)*\ldots*(X-a_q)*g[/mm]
Der Grad ist hier ja schon q also Größer als
vorausgesetzt. Also muss g=0 sein?
> für ein Polynom g. Stelle nun Gradbetrachtungen an, um zu
> zeigen, dass [mm]g=0[/mm] sein muss. Insbesondere ist damit wie
> gewünscht [mm]p_1-p_2=0[/mm].
Sry so ganz klar ist mir das noch nicht...
Danke
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:29 So 06.05.2012 | | Autor: | tobit09 |
> > Fast. Diese [mm]p_i[/mm] haben schonmal genau die [mm]a_j[/mm] für
> [mm]j\not=i[/mm]
> > als Nullstellen. Multipliziere jetzt noch jeweils mit einem
> > geeigneten Vorfaktor, damit [mm]p_i(a_i)=f(a_i)[/mm] gilt.
>
> D.h. ich multipliziere einfach jeweils noch mit einem
> Polynom [mm]g_{i}?[/mm]
Ja. (Wobei sich herausstellen wird, dass [mm] $g_i$ [/mm] sogar als Element von K gewählt werden kann.)
Nennen wir die Polynome, die du für [mm] $p_1,\ldots,p_q$ [/mm] gefunden hast, mal [mm] $p_1',\ldots,p_q'$.
[/mm]
Nun soll [mm] $p_i$ [/mm] als [mm] $p_i=g_i*p_i'$ [/mm] mit geeignetem [mm] $g_i$ [/mm] gewählt werden.
Dass [mm] $p_i$ [/mm] Vielfaches von [mm] $p_i'$ [/mm] ist, sichert gerade [mm] $p_i(a_j)=0$ [/mm] für [mm] $j\not=i$.
[/mm]
Wähle nun [mm] $g_i$ [/mm] so, dass [mm] $p_i(a_i)=f(a_i)$ [/mm] gilt, also [mm] $g_i(a_i)*p_i'(a_i)=f(a_i)$.
[/mm]
> > [mm]p_1-p_2=(X-a_1)*(X-a_2)*\ldots*(X-a_q)*g[/mm]
> Der Grad ist hier ja schon q also Größer als
> vorausgesetzt. Also muss g=0 sein?
Genau! Für [mm] $g\not=0$ [/mm] wäre der Grad der rechten Seite [mm] $\ge [/mm] q$, der Grad der linken Seite ist jedoch $<q$.
|
|
|
| |
|
moin,
Zur Uneindeutigkeit nochmal kurz:
Ist der Körper $K$ endlich mit $K = [mm] \{k_1, \ldots k_q \}$ [/mm] so betrachte das Polynom $p := [mm] (x-k_1)*(x-k_2)\cdots (x-k_q)$.
[/mm]
Dieses Polynom hat den Grad $q$, ist also insbesondere nicht das Nullpolynom.
Allerdings ist $p(x) = 0$ für alle $x [mm] \in [/mm] K$, die Abbildung $p$ ist also die Nullabbildung.
Bei endlichen Körpern muss man also zwischen Polynom und Polynomfunktion unterscheiden; insbesondere können zwei verschiedene Polynome dieselbe Polynomfunktion haben.
Das wollt ich wie gesagt nur einmal kurz an dieser Stelle erwähnen, dann wird dir vielleicht etwas klarer was das "eindeutig falls grad$(p) [mm] \leq [/mm] q$" sollte.
lg
Schadow
|
|
|
|
