# If $\gcd(m,n)=1$ then $\gcd(2m-n-1,m-1)=2$?

How to prove following statement:

If $\gcd(m,n)=1$, then $\gcd(2m-n-1,m-1)=2$, where $m,n$ are odd numbers and $m>n$.

Since $m=2k_1+1$ and $n=2k_2+1$ we may write:

$2m-n-1=2(2k_1+1)-2k_2-1-1=4k_1-2k_2=2(2k_1-k_2)$

$m-1=2k_1+1-1=2k_1$

So we may conclude that common divisor is $2$ but how to prove that it is greatest common divisor of those two numbers ?

-
$\gcd(13,5)=1$ but $\gcd(20,12)=4\ne2$... –  anon Nov 2 '11 at 19:11

## 3 Answers

If $m=9$ and $n=5$ then $\gcd(9,5) =1$ but $\gcd(2\times 9-5-1,9-1) = \gcd(12,8) =4$ so it is not true.

From your previous work, if $k_1$ and $k_2$ have a common factor but $2k_1+1$ and $2k_2+1$ do not then you will find a counterexample.

-

It is known/easy to prove that $\gcd(a,b) = \gcd (a \pm b,b)$.

This means that

$$\gcd(2m-n-1,m-1)=\gcd(m-n,m-1)=\gcd(m-n,m-1-(m-n))$$ $$= \gcd(m-n,n-1)=\gcd(m-1, n-1) \,.$$

-
Might add here that given only that $m$ and $n$ are relatively prime and odd, we can arrange for $\gcd(m-1,n-1)$ to be any even number. –  André Nicolas Nov 2 '11 at 19:42

If $m=7$ and $n=5$, then $\gcd(m,n)=1$ and $\gcd(2m-n-1,n-1)=\gcd(8,4)=4$, so it would seem the proposition is not true.

Comment added later: Someone else gave a counterexample, with $m-1$ where I had $n-1$ above. The comments below still stand. End of comment added later

Every divisor that $a$ and $b$ have in common is a divisor that $a$ and $b-a$ have in common.

Conversely, every divisor that $a$ and $b-a$ have in common is a divisor that $a$ and $b$ have in common.

Therefore the set of all common divisors of $a$ and $b$ is the same as the set of all common divisors of $a$ and $b-a$.

Therefore the greatest common divisor of $a$ and $b$ is the same as the greatest common divisor of $a$ and $b-a$, and that's why Euclid's algorithm works.

Think about applying all that to similar propositions.

Later edit: Subtracting those $1$s at the end changes things. I almost wonder if somehow a slightly different identity was intended---one that is correct. But I don't know what it would be.

-
@JavaMan I'm not following you. If $n=5$ then $n-1=4\ne6$. –  Michael Hardy Nov 2 '11 at 21:56
Oh. I see. But someone else posted another counterexample. –  Michael Hardy Nov 4 '11 at 22:03