Exercise 2.9.3

Question

Prove that $\mathrm{gcd}(x,y) = \mathrm{gcd}(U(x,y))$ for $(x,y) \in \mathbb{Z}^2$ and $U \in \mathrm{GL}(2,\mathbb{Z})$.

Richard Ganaye · Accepted Answer

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{\U}{\mathbb{U}}

\begin{proof}
Let $U = \begin{pmatrix} s & t\u & v \end{pmatrix} \in \mathrm{SL}(2,\Z)$, and $d = x \wedge y = \mathrm{gcd}(x,y)$.

Then 
\begin{align*}
(x',y') &= U(x,y) = (sx +t y, u x + vy),\
(x,y) &= U^{-1}(x',y') = (vx'-ty', -ux' + sy').
\end{align*}

Write $d' = \mathrm{gcd}(U(x,y)) = x' \wedge y'$.

Then $d \mid x, d \mid y$, thus $d \mid sx+ty = x', d \mid ux + vy = y'$, therefore $d \mid x' \wedge y' = d'$.

Similarly, $d' \mid x', d' \mid y'$, thus $d' \mid vx' - ty' = x, d \mid-ux' + sy' = y$, therefore $d' \mid x \wedge y = d$.

Since $d \mid d'$, and $d' \mid d$, where $d \geq 0, d' \geq 0$, we conclude $d = d'$.

\end{proof}

Answers