Show that the gcd of an odd integer and an even integer is odd I am using the definition of odd and even integers along with bezout's theorem and I end up with something of the form $d=(2k)m+(2l+1)p$ where $a=2k$ and $b=2l+1$. I've tried to use contradiction as well but I keep running into dead ends. I know I'm glossing over something trivial and need some advice.
 A: The gcd of two numbers is, among other things, a common divisor.  An odd number has no even divisors, so the gcd cannot be even.
A: This is a simple proof by contradiction.
Recall that gcd denotes "greatest common divisor".
By definition:
(1) Let ev denote an even integer
(2) Let od denote an odd integer
Assume for contradiction purposes:
(3) gcd( ev, od) is even
Hence:
(4) 2 is a common divisor of both ev and od.
If 2 divides od then od is an even integer.
However this contradicts statement (2).
So our assumption at statement (3) is false.  Thus:
(5) gcd( ev, od) is odd

A: Suppose $a$ is an even integer and $b$ an odd integer. Then there are integers $k$ and $m$ such that 
$$a=2k$$
$$b=2m+1$$
Let $d=gcd(a,b)$. Therefore, $d|a$ and $d|b$. Consequently, there are integers $x$ and $y$ such that
$$a=2k=dx$$
$$b=2m+1=dy$$
Adding the two equations renders
$$a+b=2(k+m)+1=d(x+y)$$
So the product $d(x+y)$ is odd, which is only possible if $d$ and $(x+y)$ are odd.
Therefore, $d$ is odd, leading us to conclude that the gcd of an odd and even number is odd.
