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.
[Math] Show that the gcd of an odd integer and an even integer is odd
divisibilitynumber theory
Related Solutions
Yes. The generalization is provided by modular arithmetic. The properties you are observing all come from the fact that taking the remainder modulo $n$ respects addition and multiplication, and this generalizes to any $n$. More generally in abstract algebra we study rings and their ideals for the same reasons.
The notion of evenness and oddness of functions is closely related, but it is somewhat hard to explain exactly why. The key point is that there is a certain group, the cyclic group $C_2$ of order $2$, which is behind both concepts. For now, note that the product of two even functions is even, the product of an even and odd function is odd, and the product of two odd functions is even, so even and odd functions under multiplication behave exactly the same way as even and odd numbers under addition.
There are also huge generalizations depending on exactly what you're looking at, so it's hard to give a complete list here. You mentioned chessboards; there is a more general construction here, but it is somewhat hard to explain and there are no good elementary references that I know of. Once you learn some modular arithmetic, here is the modular arithmetic explanation of the chessboard idea: you can assign integer coordinates $(x, y)$ to each square (for example the coordinate of the lower left corner), and then you partition them into black or white squares depending on whether $x + y$ is even or odd; that is, depending on the value of $x + y \bmod 2$. Then given two points $(a, b)$ and $(c, d)$ you can consider the difference $c + d - a - b \bmod 2$, and constraints on this difference translate to constraints on the movement of certain pieces. This idea can be used, for example, to prove that certain chessboards (with pieces cut out of them) cannot be tiled with $1 \times 2$ or $2 \times 1$ tiles because these tiles must cover both a white square and a black square. Of course there are generalizations with $2$ replaced by a larger modulus and larger tiles.
As for matrices and vectors, let's just say that there are a lot of things this could mean, and none of them are straightforward generalizations of the above concept.
One easy and insightful way is to use the proof below. It essentially constructs $\rm\:gcd\:$ from $\rm\:lcm\:$ by employing duality between minimal and maximal elements - see the Remark below. This is essentially how the linked Wikipedia proof works, but there the innate duality is obfuscated by the presentation. Below is a proof structured so that this fundamental duality is brought to the fore.
$\rm{\bf Theorem}\quad c\mid a,b\iff c\mid d,\ \ $ for $\rm\ \ d = ab/lcm(a,b).\ $ $\rm\color{#0a0}{Hence}$ $\rm\ d = gcd(a,b)$
$\rm{\bf Proof}\qquad\ \ \, c\mid a,b \iff a,b\mid ab/c \iff lcm(a,b)\mid ab/c \iff c\mid ab/lcm(a,b)$
$\rm\color{#0a0}{Generally}\,$ if $\rm\, c\mid a,b\iff c\mid d\ $ then $\rm\ d = \gcd(a,b)\ $ up to unit factors, i.e. they're associate.
Indeed setting $\rm\:c = d\:$ in direction $(\Leftarrow)$ shows that $\rm\:d\mid a,b,\:$ i.e. $\rm\:d\:$ is a common divisor of $\rm\:a,b.\:$ Conversely, by direction $(\Rightarrow)$ we deduce that $\rm\:d\:$ is divisible by every common divisor $\rm\:c\:$ of $\rm\:a,b,\:$ thus $\rm\:c\mid d\:\Rightarrow\: c\le d,\:$ so $\rm\:d\:$ is a greatest common divisor (both divisibility and magnitude-wise).
Remark $\ $ The proof shows that, in any domain, if $\rm\:lcm(a,b)\:$ exists then $\rm\:gcd(a,b)\:$ exists and $\rm\ gcd(a,b)\,lcm(a,b) = ab\ $ up to unit factors, i.e. they are associate. The innate duality in the proof is clarified by employing the involution $\rm\ x'\! = ab/x\ $ on the divisors of $\rm\:ab.\:$ Let's rewrite the proof using this involution (reflection).
Notice that $\rm\ x\,\mid\, y\:\color{#c00}\iff\: y'\mid x'\,\ $ by $\smash[t]{\,\ \rm\dfrac{y}x = \dfrac{x'}{y'} \ }$ by $\rm\, \ yy' = ab = xx',\ $ so rewriting using this
$\begin{eqnarray}\rm the\ proof\ \ \ c\mid a,b &\iff&\rm b,\,a\mid ab/c &\iff&\rm lcm(b,\,a)\mid ab/c &\iff&\rm c\mid ab/lcm(b,a)\\[.5em] \rm becomes\ \ \ \ c\mid a,b &\color{#c00}\iff&\rm a',b'\mid c' &\iff&\rm lcm(a',b')\mid c' &\color{#c00}\iff&\rm c\mid lcm(a',b')'\end{eqnarray}$
Now the innate duality is clear: $\rm\ gcd(a,b)\,=\,lcm(a',b')'\ $ by the $\rm\color{#0a0}{above}$ gcd characterization.
Best Answer
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.