ggT-Erhaltung bei Multiplikation mit einer in Z invertierbaren 2x2-Matrix

[Phoemuex]

Ich habe folgendes Problem:

Wenn ich eine Spalte $v := \left(\begin{array}{c}a \\ b\end{array}\right) \in \mathbb{Z}^{2 \times 1}$ und eine Matrix $A := \left(\begin{array}{cc}A_{1,1} & A_{1,2} \\ A_{2,1} & A_{2,2}\end{array}\right) \in \mathbb{Z}^{2 \times 2}$ habe, die in $\mathbb{Z}$ invertierbar ist, für die also gilt $A^{-1} \in \mathbb{Z}^{2 \times 2}$, dann soll ich zeigen, dass für $\left(\begin{array}{c}a' \\ b' \end{array}\right) := A \cdot v$ gilt: $ggT(a,b) = ggT(a',b')$.

Ich weiß, dass das Inverse zu $A$ gerade $\frac{1}{A_{1,1} \cdot A_{2,2} - A_{1,2} \cdot A_{2,1}} \cdot \left(\begin{array}{cc}A_{2,2} & -A_{1,2} \\ -A_{2,1} & A_{1,1}\end{array}\right)$ ist, also muss für $A^{-1} \in \mathbb{Z}^{2 \times 2}$ gelten $A_{1,1} \cdot A_{2,2} - A_{1,2} \cdot A_{2,1} | A_{i,j} \, \forall i,j \in \underline{2}$.

Aber wirklich weiterhelfen tut mir das auch nicht... Habt ihr vielleicht eine Idee?

Felix

[.filmor]

Vielleicht mal den erweiterten euklidischen Algorithmus auf ggT((a_11 + a_21) * a, (a_12 + a_22) * b) werfen und (hoffentlich ;)) sehen, dass die beiden Vorfaktoren für det(A)^-1 in Z unabhängig von a_ij sind.

[Christoph]

Ich hab mit Phoemux im #cpp-Chat darueber geredet. Hier eine kurze Skizze, wie man das angehen koennte:

Man weiss, dass a' und b' Linearkombinationen von a und b sind. Also liegen a' und b' beide im Ideal (a) + (b) = ( ggT(a,b) ). Also sind a' und b' beides Vielfache von ggT(a,b), damit ist ggT(a', b') >= ggT(a, b).

Da man A invertieren kann, kann man es auf die andere Seite stellen und bekommt, dass a und b Linearkombinationen von a' und b' sind. Durch dasselbe Argument wie oben bekommt man dann ggT(a', b') <= ggT(a, b).

Zusammen ergibt das ggT(a', b') = ggT(a, b).

Eventuell muss man noch ein paar Spezialfaelle separat behandeln, wie a=b=0.

[Christoph]

Kurz nachdem ich den obigen Post abgesendet hatte, ist mir eingefallen, dass es auch ohne Ideale nicht viel komplizierter wird. Wir wissen a' = x*a + y*b fuer irgendwelche ganzen Zahlen x, y die aus der Matrix stammen. Sei d der ggT von a und b. Dann teilt d sowohl a als auch b, und damit auch a'. Analog bekommt man dass d auch b' teilt. Dann geht es weiter wie in meinem letzten Post.