1
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.