Polynome ggT

03.12.2004, 17:33

wsch

Auf diesen Beitrag antworten »

Polynome ggT

Hallo,

bei T(x)=ggT(P,Q) (x)

P(x)= x^3 +x²+4x+1
Q(x)=x²+x+1

wenn ich es so rechne wie ich mit normallen zahlen rechne, kommt bei mir T(x)=-27/13*1/x+9/13 raus

könnte das sein, oder hab ich da was falsch gemacht?

muss mit dieser zahl nämlich weiter rechnen ...

03.12.2004, 17:39

klarsoweit

Auf diesen Beitrag antworten »

RE: Polynome ggT
wie hast du denn das gemacht?
Zerlege P(x) und Q(x) in Linearfaktoren. Daraus kannst du dann den ggT ermitteln.
Und was ist x4x ?

03.12.2004, 17:41

wsch

Auf diesen Beitrag antworten »

ist falsch!!!

hab was übersehen

P(x) und Q(x) ist element aus Z7[x] ....

dh. ich soll so dividieren als ob es ein körper wäre?

was wäre dann z.b. x^3/x^2 ? noch immer x oder was anderes?

das soll man nach euklidischen Algorithmus berechnen können?

03.12.2004, 17:50

klarsoweit

Auf diesen Beitrag antworten »

habe gerade festgestellt, dass x² + x + 1 keine Nullstellen hat.
Jetzt stehe ich selbst auf dem Schlauch. verwirrt

verwirrt

Hat jemand noch ne Idee?

03.12.2004, 17:54

wsch

Auf diesen Beitrag antworten »

das liegt wohl daran dass P(x) und Q(x) element von Z7[x] ist.

jetzt weiß ich leider nicht, wie ich daraus Linearfaktoren berechne, bzw. ggT finde ..

03.12.2004, 20:00

Gustav

Auf diesen Beitrag antworten »

Meinst du mit Z7[x] den Ring Z modulo 7 adjungiert x?

Anzeige

03.12.2004, 23:30

wsch

Auf diesen Beitrag antworten »

Zitat:

Original von Gustav
Meinst du mit Z7[x] den Ring Z modulo 7 adjungiert x?

ja genau Z7[x] den Ring Z modulo 7 (ist eingentlich Körper nicht Ring)

weiß leider nicht was adjungiert heißt

04.12.2004, 08:19

Leopold

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \mathbb{Z}_7 \end{eqnarray*}$ ist ein Körper, $\begin{eqnarray*} \mathbb{Z}_7[x] \end{eqnarray*}$ ist ein Ring. Der Ring $\begin{eqnarray*} \mathbb{Z}_7[x] \end{eqnarray*}$ ist euklidisch, zur Berechnung des $\begin{eqnarray*} \operatorname{ggT} \end{eqnarray*}$ kann daher der euklidische Algorithmus verwendet werden:

$\begin{eqnarray*} \operatorname{ggT}(a,b) = \operatorname{ggT}({b,a \operatorname{mod} b}) \end{eqnarray*}$

Mit $\begin{eqnarray*} a \operatorname{mod} b \end{eqnarray*}$ ist der Rest bei der Division von $\begin{eqnarray*} a \end{eqnarray*}$ durch $\begin{eqnarray*} b \end{eqnarray*}$ gemeint. Die Formel wird so oft angewandt, bis das eine Glied ein Teiler des anderen ist.

Beispiel in $\begin{eqnarray*} \mathbb{Z} \end{eqnarray*}$
gesucht: $\begin{eqnarray*} \operatorname{ggT}(2100,648) \end{eqnarray*}$

2100 = 648 · 3 + 156
$\begin{eqnarray*} \operatorname{ggT}(2100,648) = \operatorname{ggT}(648,156) \end{eqnarray*}$

648 = 156 · 4 + 24
$\begin{eqnarray*} \operatorname{ggT}(648,156) = \operatorname{ggT}(156,24) \end{eqnarray*}$

156 = 24 · 6 + 12
$\begin{eqnarray*} \operatorname{ggT}(156,24) = \operatorname{ggT}(24,12) = 12 \end{eqnarray*}$

Also ist $\begin{eqnarray*} \operatorname{ggT}(2100,648) = 12 \end{eqnarray*}$ .

Und ganz analog geht das in $\begin{eqnarray*} \mathbb{Z}_7[x] \end{eqnarray*}$ . Hier steht jetzt

$\begin{eqnarray*} P \operatorname{mod} Q \end{eqnarray*}$

für den Rest, wenn man mit den Polynomen $\begin{eqnarray*} P,Q \end{eqnarray*}$ die Polynomdivision durchführt.

Ich mache einmal den ersten Schritt:

$\begin{eqnarray*} P(x) = x^3 + x^2 + 4x + 1 \end{eqnarray*}$
$\begin{eqnarray*} Q(x) = x^2 + x + 1 \end{eqnarray*}$

x³ + x² + 4x + 1 = (x² + x + 1) · x + (3x + 1)
x³ + x² + x
-----------
..........3x + 1

Daher gilt:

$\begin{eqnarray*} \operatorname{ggT}(x^3 + x^2 + 4x + 1 \; , \; x^2 + x + 1) = \operatorname{ggT}(x^2 + x + 1 \; , \; 3x + 1) \end{eqnarray*}$

Und den nächsten und letzten Schritt solltest du jetzt selbst machen.
Beachte: Die Rechnungen bei den Koeffizienten der Polynome müssen über $\begin{eqnarray*} \mathbb{Z}_7 \end{eqnarray*}$ durchgeführt werden. Dort gilt z.B. $\begin{eqnarray*} 3 \cdot 5 = 1 \end{eqnarray*}$ oder $\begin{eqnarray*} 1 - 5 = 3 \end{eqnarray*}$ . Bei dem ersten von mir durchgeführten Schritt fällt das nämlich nicht auf.

04.12.2004, 11:38

wsch

Auf diesen Beitrag antworten »

also wenn ich das weiter fortführe:

(x²+x+1) / (3x+1)=1/5x-???
-(x²+1/5x)
--------------
-4/5x+1

jetzt finde ich weiter keine Zahl die x*3=4/5 ergibt

wenn ich es so rechne:

3*x=4/5
x=4/5*1/3 = 4/1 weil (4*1= 4 und 5*3=1 ist)

wenn ich jetzt für x 4 einsetzte = 3*4 bekomme ich 5 raus und nicht 4/5 !

Wie soll man es in Z7 sonst rechnen?

04.12.2004, 11:48

Leopold

Auf diesen Beitrag antworten »

Beachte, daß in $\begin{eqnarray*} \mathbb{Z}_7 \end{eqnarray*}$ gilt: $\begin{eqnarray*} 5 \cdot 3 = 1 \end{eqnarray*}$ , also $\begin{eqnarray*} \frac{1}{3} = 5 \end{eqnarray*}$

Du kannst die Sache natürlich auch ganz anders angehen, indem du die beiden Polynome in irreduzible Bestandteile zerlegst. Dazu würde ich zunächst einmal die jeweiligen Nullstellen bestimmen. Das geht durch Probieren, da man ja nur die 7 Elemente von $\begin{eqnarray*} \mathbb{Z}_7 \end{eqnarray*}$ durchtesten muß.

04.12.2004, 12:02

pimaniac

Auf diesen Beitrag antworten »

Viel einfacher gehts so:

Der ggT von zwei Polynomen kann höchstens ein Polynom vom Grad des gradkleineren der beiden Polynome sein.

--> Wenn du dir den ggT der beiden Polynome für x=0,1 und 2 ausrechnest kannst du mit dem unbestimmten Ansatz
ggT(P(x),Q(x))=a*x^2+b*x+c a,b und c ausrechnen.

04.12.2004, 12:44

Leopold

Auf diesen Beitrag antworten »

Ich schreibe hier die Rechnung mit dem Euklidischen Algorithmus einmal vollständig auf.

$\begin{eqnarray*} P(x) = x^3 + x^2 + 4x + 1 \end{eqnarray*}$
$\begin{eqnarray*} Q(x) = x^2 + x + 1 \end{eqnarray*}$

$\begin{eqnarray*} \begin{matrix} x^3 & + & x^2 & + & 4x & + & 1 & = & (x^2 + x + 1) \cdot x + (3x + 1) \\ -(x^3 & + & x^2 & + & x & & ) & & \\ & & & & 3x & + & 1 & & \end{matrix} \end{eqnarray*}$

$\begin{eqnarray*} \begin{matrix} x^2 & + & x & + & 1 & = & (3x + 1) \cdot (5x + 1) \\ -(x^2 & + & 5x & & ) & & \\ & & 3x & + & 1 & & \\ -( & & 3x & + & 1) & & \\ & & & & 0 & & \end{matrix} \end{eqnarray*}$

Jetzt geht die Division auf. Der $\begin{eqnarray*} \operatorname{ggT} \end{eqnarray*}$ ist gefunden:

$\begin{eqnarray*} \operatorname{ggT}(x^3 + x^2 + 4x + 1 , x^2 + x + 1) = \operatorname{ggT}(x^2 + x + 1 , 3x + 1) = 3x + 1 \end{eqnarray*}$

Der $\begin{eqnarray*} \operatorname{ggT} \end{eqnarray*}$ ist nicht eindeutig bestimmt. Man hat die Freiheit, mit einer beliebigen Einheit des Ringes $\begin{eqnarray*} \mathbb{Z}_7[x] \end{eqnarray*}$ (das sind gerade die Elemente $\begin{eqnarray*} \neq 0 \end{eqnarray*}$ von $\begin{eqnarray*} \mathbb{Z}_7 \end{eqnarray*}$ ) durchzumultiplizieren. Man kann z.B. mit 5 durchmultiplizieren:

$\begin{eqnarray*} \operatorname{ggT}(x^3 + x^2 + 4x + 1 , x^2 + x + 1) = 5 \cdot (3x + 1) = x + 5 = x -2 \end{eqnarray*}$

Auf diese Weise erhält man den $\begin{eqnarray*} \operatorname{ggT} \end{eqnarray*}$ in normierter Darstellung (höchster Koeffizient ist 1).

Der Vorteil des Euklidischen Algorithmus ist, daß man zur Berechnung des $\begin{eqnarray*} \operatorname{ggT} \end{eqnarray*}$ die Faktorzerlegung der Polynome nicht kennen muß. In diesem konkreten Fall geht es aber mit der Faktorzerlegung einfacher, da man die Nullstellen der Polynome sofort bestimmen kann.

Versuche diesen zweiten Weg einmal alleine.

04.12.2004, 14:03

wsch

Auf diesen Beitrag antworten »

hab durch deine Rechnung meine Fehler gefunden, danke.

die Aufgabe geht weiter, hab aber selbst gelöst - will hier nur mal Aufgabe + meine Lösung aufschreiben:

Finden Sie für die Polynome P(x) und Q(x) $\begin{eqnarray*} \in \end{eqnarray*}$ Z 7 [x] das Polynom
T(x) := ggT(P,Q) (x)
und geben Sie außerdem Polynome A(x) $\begin{eqnarray*} \in \end{eqnarray*}$ Z 7 [x] und B(x) $\begin{eqnarray*} \in \end{eqnarray*}$ Z 7 [x] an so, daß
A(x) × P(x) + B(x) × Q(x) = T(x)
a) P(x) = x 3 + x 2 + 4 x + 1, Q(x) = x 2 + x + 1

Meine Lösung:

T(x)=3x+1

A(x)*(x^3+x²+4x+1) + B(x)*(x²+x+1)=3x+1
=
3x+1=A(x)*(5x²+x+1)+B(x)*5x+1=3x+1
=
A(x)*(5x²+x+1)+B(x)*5x+1=1
=
(1/(3x²+2x+2))*(5x²+x+1)+(1/(3x+2))*(5x+1)=1
=
4+4=1

also:
A(x)= 1/(3x²+2x+2)
B(x)= 1/(3x+2)

müsste richtig sein, oder?

04.12.2004, 17:55

Leopold

Auf diesen Beitrag antworten »

Dein $\begin{eqnarray*} A(x) \end{eqnarray*}$ und $\begin{eqnarray*} B(x) \end{eqnarray*}$ sind keine Polynome. Das ist daher nicht im Sinne der Aufgabe. Im übrigen verstehe ich deine Rechnung nicht.

Betrachte stattdessen die Gleichung:

$\begin{eqnarray*} x^3 + x^2 + 4x + 1 = (x^2 + x + 1) \cdot x + (3x + 1) \end{eqnarray*}$

04.12.2004, 19:37

wsch

Auf diesen Beitrag antworten »

warum ist mein A(x) und B(x) keine Polynome?

deine Gleichung verstehe ich, aber ich soll für T(x)=3x+1

rausfinden was A(x)*(x^3+x²+4x+1) + B(x)*(x²+x+1)=T(x) ist.

und mit meinem A(x) und B(x) kommt es raus

05.12.2004, 21:55

Leopold

Auf diesen Beitrag antworten »

Deine A(x),B(x) sind gebrochen-rational, nicht ganzrational. Somit sind das keine Polynome.

06.12.2004, 23:53

wsch

Auf diesen Beitrag antworten »

ich weiß aber nicht, wie ich sonst auf das Ergebnis kommen soll .... ?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »