elementary number theory - Help with indirect proof $gcd(9k+4,2k+1)=1$

Show: $\gcd(9k+4,2k+1)=1 ~~ \forall k\in \mathbb Z$

Indirect proof.

If  $1\neq d=\gcd(9k+4,2k+1)~\exists k\in \mathbb Z$,
then $d$ has to be of the form $2m+1$ for an integer $m$.

That somehow throws me back at the beginning.

Answer

Please excuse me for this messed up question,
but I've come up with an answer as compensation:

Just apply the Euclidean algorithm, and in 3 lines you get 1 as GCD.