## Loser66 one year ago Show that gcd (even, odd) = odd Please, help

1. Loser66

@zzr0ck3r

2. zzr0ck3r

if it was even, then an even number divides an odd number, yikes!

3. Loser66

I need algebraic proof, not logic one. Please.

4. Loser66

even = 2k odd = 2m +1 gcd (2k, 2m +1) = d, and prove d is odd.

5. Empty

This troubles me

6. zzr0ck3r

Suppose by way of contradiction that $$c=\gcd(2k, 2k_0+1)$$ where $$c=2k_2$$ is even. Then $$2k_0+1=2(2k_2)$$

7. Loser66

This is what I have: d| 2k d| 2m +1 hence d| 2k + 2m +1 d| 2(k+m) +1 then ... stuck.

8. zzr0ck3r

Then $$2k_0+1=k(2k_2)$$ for osme $$k$$.

9. Loser66

From where, you have $$2k_0 +1 = 2 (2k_2)$$?

10. zzr0ck3r

that should say $2k_0+1=k(2k_2)$

11. Loser66

Use other letter, please, it confuses me when the fist element is k, and this k.

12. Loser66

Got you.!! thanks a lot

13. zzr0ck3r

lol ok PF Suppose $$a$$ is even, $$b$$ is odd. Then $$b=2k_1+1$$ for some $$k_1\in \mathbb{Z}$$. Now suppose $$c=\gcd(a,b)$$ and $$c$$ is even. Then $$c=2k_2$$ for some $$k_2\in \mathbb{Z}$$. Since $$c$$ is the GCD of $$a$$ and $$b$$ it must divide both. So $$c$$ divdes $$b$$ and thus $$b=c*k_3$$ where $$k_3\in \mathbb{Z}$$ So $$2k_1+1=k_3(2k_2)$$ a contradiction

14. zzr0ck3r

an even number cant divide an odd number evenly is actually what you prove.

15. zzr0ck3r

np