Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
3  
$\gcd(13,5)=1$ but $\gcd(20,12)=4\ne2$... –  anon Nov 2 '11 at 19:11

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer

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

share|improve this answer
2  
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.

share|improve this answer
    
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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