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?


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.


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$



  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$

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