All variables are integers:
conclude that if, in addition, $ad − bc = \pm 1$, then
$\gcd(x, y) = \gcd(ax + by, cx + dy)$.
The fact that $\gcd(x, y) = \gcd(x + ky, y)$ used for the Euclidean Algorithm is a special case of this exercise.
I was also told to consider the idea of a matrix $\begin{pmatrix} a & b\\ c & d\end{pmatrix}$ as well as its inverse.
I understand that $ad-bc$ is the determinant and that the determinant of the inverse is still equal to $ad-bc$ as well but I'm not able to put the pieces together about how this helps me to show the two gcds are equal.
Answer
Let $A := \begin{pmatrix}a & b\\c & d\end{pmatrix}$. The condition that $ad-bc = \pm 1$ means that $A^{-1}$ also has integer coefficients. If you have integers $u,v$ with $ux+vy = {\rm gcd}(x,y)=: z$, then letting $B:= (u,v)$, we have $B\cdot (x, y)^T = z$. But then also
$$
z = BA^{-1} A\cdot \begin{pmatrix} x \\ y \end{pmatrix} = BA^{-1}\cdot \begin{pmatrix} ax + by\\ cx + dy\end{pmatrix},
$$
so, if $BA^{-1}=: (n,m)$, then $n\cdot (ax+by) + m\cdot (cx+dy) = z$, which shows that ${\rm gcd}(ax+by, cx+dy)$ divides $z = {\rm gcd}(x,y)$.
Interchanging the roles of $\begin{pmatrix} x\\ y\end{pmatrix}$ and $\begin{pmatrix} ax+by\\ cx+dy\end{pmatrix}$ as well as of $A$ and $A^{-1}$ shows that ${\rm gcd}(x,y)$ divides ${\rm gcd}(ax+by, cx+dy)$, which shows that both are equal.
No comments:
Post a Comment