Aufgabe: Berechnen SIe über Z_5 das Inverse von $$x^3 + x + 1$$ modulo $$x^5+x^2+2$$ mit dem erweiterten Euklidischen Algorithmus.
$$\begin{matrix} a && b & &y \\ \hline x^5+x^2 + 2 &|& &|& 0 \\ \hline x^3 + x + 1 &|& x^2+4 &|& 1 \\ \hline x + 3 &|& x^2 + 2x &|& 4x^2+1 \\ \hline 1 &|& &|& \gamma \end{matrix}$$
Die Spalte x habe ich bewusst weggelassen
Die Tabelle ist soweit richtig. Nur bei der Berechnung des letzten y (hier Gamma) komme ich einfach nicht auf das richtige Ergebnis.
Normalerweise würde man wie die Tabelle gerade aussieht y_i ja als
$$y_i = \begin{Bmatrix} 0 & \text{, falls} & i = 0 \\ 1 & \text{, falls} & i = 1 \\ y_{i-2} - y_{i-1} \cdot b_{i-1} & \text{, falls} & sonst \end{Bmatrix}$$
berechnen. Doch dort würde für gamma folgendes rauskommen
$$1 - (x^2 + 2x)(4x^2+1) = (x^2 + 2x)(4x^2+1) - 1 = 4x^4 + x^2 + 8x^3 + 2x - 1 \\ Z_5 \text{ ausnutzen } \rightarrow 4x^4 + x^2 + 8x^3 + 2x - 1 = 4x^4 + 3x^3 + x^2 + 2x + 4$$
Und der Test ergibt, dass dieser Wert nicht gleich der Inverse ist.
$$\text{Test: } (4x^4 + 3x^3 + x^2 + 2x + 4) \cdot (x^3 + x + 1) \; mod{(x^5 + x^2 + 2)} \equiv 1 \\ \\ (4x^4 + 3x^3 + x^2 + 2x + 4) \cdot (x^3 + x + 1) = \\ \begin{matrix} 4x^7 &+ 3x^6 &+ x^5 &+ 2x^4 &+ 4x^3 \\ &&+4x^5 &+ 3x^4 &+ x^3 &+ 2x^2 &+ 4x \\ &&&+4x^4 &+ 3x^3 &+ x^2 &+ 2x &+ 4 \\ \\ \hline 4x^7 &+ 3x^6 &+ 5x^5 &+ 9x^4 &+ 8x^3 &+ 3x^2 &+ 6x &+ 4 \end{matrix}$$
$$\frac{4x^7 + 3x^6 + 5x^5 + 9x^4 + 8x^3 + 3x^2 + 6x + 4}{x^5 + x^2 + 2} \\\\\\ \begin{matrix} (4x^7 &+ 3x^6 &+ 5x^5 &+ 9x^4 &+ 8x^3 &+ 3x^2 &+ 6x &+ 4) & / & (x^5 + x^2 + 2) &= 4x^2 + 3x \\ -(4x^7 &&&+ 4x^4 &&+ 8x^2)&&\\ \hline = & (3x^6 &+ 0 &+ 0 &+ 8x^3 &+ 0x^2 &+ 6x &+ 4) & & \\ &-(3x^6&&&+3x^3&&+6x)& \\ \hline = &&&&0&&2x&+4 & \leftarrow Rest \neq 1 \end{matrix} \\$$
Könnte mir jemand eventuell sagen was ich falsch mache?
LG
