Prove that if $\gcd(m, n) > 1$, then there do not exist integers $x, y$ so that $mx + ny = 1$.

Question

I've been stuck on this one for awhile, and I thought that if I did a contradiction: if $\gcd(m,n) > 1$ then for all integers $x,y$, $ax + ny \neq 1$. I could simply prove it wrong by giving an example. But I've got a feeling that I'm missing something that makes this not work, But I don't know what else to do.

Answer 1

$\mathrm{gcd}(m,n)$ divides $mx+ny$ for all $x,y\in\Bbb{Z}$, and only $1$ divides $1$.

Answer 2

As the comments noted, the contradiction assumptions in the original question are not correct. The correct assumption (and some hints of how to proceed) follow:

Suppose that $\gcd(m,n)=d>1$ and suppose that there exist integers $x$ and $y$ so that $mx+ny=1$. Since $d$ divides both $m$ and $n$ (since it is the greatest common divisor of them), $d$ divides the LHS. So $d$ divides the RHS. Now, can you find a contradiction?