$gcd(m,n) = gcd(a\cdot m+b\cdot n,c\cdot m+d\cdot n)$

Question

Intento probar la siguiente afirmación:

Dejemos que $a,b,c,d \in\mathbb{Z}$ y $m,n \in \mathbb{N}$ .
Si $ad-bc = 1$ entonces $gcd(m,n) = gcd(a\cdot m+b\cdot n,c\cdot m+d\cdot n)$ .

1. Así que, en primer lugar, he definido el gcd de $m$ y $n$ como $x$ :

   $x := gcd(m,n)$ .

2. $m = x\cdot k$

3. $n = x\cdot l$

4. $gcd(m,n) = gcd( a\cdot x\cdot k+b\cdot x\cdot l , c\cdot x\cdot k+d\cdot x\cdot l )$

5. $gcd(m,n) = gcd( x(a\cdot k+b\cdot l) , x(c\cdot k+d\cdot l) )$

Pero a partir de ahí no sé cómo proceder. Supongo que tengo que utilizar de alguna manera el $ad-bc=1$ ecuación pero no sé cómo.

También intenté utilizar el lema de Bezout, pero tampoco funcionó.

¿Sabéis cómo continuar la prueba?

Answer 1

Si $p$ divide $am+bn,cm+dn$

$p$ debe dividir $c(am+bn)-a(cm+dn)=n(bc-ad)=?$

y $d(am+bn)-b(cm+dn)=?$

Por el contrario, si $q$ divide $m,n$

$q$ dividirá $am+bn,cm+dn$

Answer 2

Pistas:

1. Si $x$ y $y$ son combinaciones lineales de $m,n$ entonces $\gcd(m,n)\mid \gcd(x,y)$
2. Para $ad-bc=1$ , $m$ y $n$ son combinaciones lineales de $am+bn$ y $cm+dn$