1
$\begingroup$

This question already has an answer here:

I'm trying to proof the following statement:

Let $a,b,c,d \in\mathbb{Z}$ and $m,n \in \mathbb{N}$.
If $ad-bc = 1$, then $gcd(m,n) = gcd(a\cdot m+b\cdot n,c\cdot m+d\cdot n)$.

  1. So first of all I defined the gcd of $m$ and $n$ as $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) )$

But from there on I don't know how to proceed. I guess I have to somehow use the $ad-bc=1$ equation but I don't know how.

I also tried to use the Lemma of Bezout but that didn't work either.

Do you guys know how to continue the proof?

$\endgroup$

marked as duplicate by Bill Dubuque, Community Jan 16 at 21:10

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

If $p$ divides $am+bn,cm+dn$

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

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

Conversely, if $q$ divides $m,n$

$q$ will divide $am+bn,cm+dn$

$\endgroup$
1
$\begingroup$

Hints:

  1. If $x$ and $y$ are linear combinations of $m,n$, then $\gcd(m,n)\mid \gcd(x,y)$
  2. For $ad-bc=1$, $m$ and $n$ are linear combinations of $am+bn$ and $cm+dn$
$\endgroup$

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