3
$\begingroup$

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 ?

  • 4
    $\gcd(13,5)=1$ but $\gcd(20,12)=4\ne2$...2011-11-02

3 Answers 3

2

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.

1

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.

  • 0
    Oh. I see. But someone else posted another counterexample.2011-11-04
0

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) \,.$

  • 3
    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.2011-11-02