Question

Show that gcd (even, odd) = odd
Please, help

Answer 1

@zzr0ck3r

Answer 2

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

Answer 3

I need algebraic proof, not logic one. Please.

Answer 4

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

Answer 5

This troubles me

Answer 6

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)\)

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

that should say

\[2k_0+1=k(2k_2)\]

Answer 11

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

Answer 12

Got you.!! thanks a lot

Answer 13

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

Answer 14

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

Answer 15

np