Exercise 1.3.23 (If $ad -bc = \pm 1, u = am + bn, v = cm + dn$, then $(m,n) = (u,v)$)

Question

Given integers $a,b,c,d, m, n, u, v$ satisfying $ad -bc = \pm 1, u = am + bn, v = cm + dn$, prove that $(m,n) = (u,v)$.

Richard Ganaye · Accepted Answer

\begin{proof} From
\begin{align}
\left\{
\begin{array}{ll}
u & = am + bn,\
v &= cm+dn,
\end{array}
ight.
\end{align}
we deduce
$$
\left\{
\begin{array}{ll}
\phantom{-}du -bv & = (ad -bc) m,\
-cu + bv &= (ad -bc)n.
\end{array}
ight.
$$
Since $ad - bc = \varepsilon = \pm 1$,
\begin{align}
\left\{
\begin{array}{ll}
m &=\phantom{-}\varepsilon du - \varepsilon bv ,\
 n &= -\varepsilon cu + \varepsilon bv 
\end{array}
ight.
\end{align}

For any integer $d$, if $d \mid m$ and $d \mid n$, then (1) shows that $d \mid u$ and $d \mid v$, thus $d \mid u \wedge v$. In particular $m\wedge n \mid u \wedge v$.

For any integer $d$, if $d \mid u$ and $d \mid v$, then (2) shows that $d \mid m$ and $d \mid n$, thus $d \mid m \wedge n$. In particular $u\wedge v \mid m \wedge n$.

Since $m\wedge n \mid u \wedge v$ and $u\wedge v \mid m \wedge n$, where $u\wedge v \geq 0, m\wedge n$, we obtain
$$m\wedge n =  u \wedge v.$$
\end{proof}

Exercise 1.3.23 (If $ad -bc = \pm 1, u = am + bn, v = cm + dn$, then $(m,n) = (u,v)$)

Answers

Comments

Exercise 1.3.23 (If $ad -bc = \pm 1, u = am + bn, v = cm + dn$, then $(m,n) = (u,v)$)

Answers

Comments

Add answer