# $gcd(m,n) = gcd(a\cdot m+b\cdot n,c\cdot m+d\cdot n)$ [duplicate]

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.

• – Bill Dubuque Jan 16 at 20:35

## 2 Answers

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$$

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$$