Necessary and Sufficient Conditions for the pair of integers $\{m,n\}$ to generate $\mathbb{Z}$

Question

Let $m,n \in \mathbb{Z}$ be two non zero numbers. I need to find necessary and sufficient conditions on $m$ and $n$ for which the pair $\{m,n\}$ generates the additive group $\mathbb{Z}$.

I made an attempt at a proof, and would like to know if 1) It's correct, and 2) if there's anything I can do to make it better.

First of all, I asserted that a necessary and sufficient condition would be for $\mathbf{\gcd(m,n)=1}$.

Now, here's my proof:

$(\implies)$ Suppose that $\gcd(m,n)=1$. Then, by Bezout's Identity, $\exists$ integers $p,q$ such that $mp+nq = \gcd(m,n)=1$.

Let $k$ be an arbitrary element of $\mathbb{Z}$. Then, we can produce $k$ by multiplying both sides of $mp+nq = 1$ through by $k$ to yield $m(pk)+n(qk)=k$.

Defining $x=pk \in \mathbb{Z}$ and $y = qk \in \mathbb{Z}$, we see that $\forall k \in \mathbb{Z}$, $\exists x, y \in \mathbb{Z}$ such that $mx+ny=k$.

So, $<m,n>=\mathbb{Z}$.

$(\Longleftarrow)$ Suppose $<m,n>=\mathbb{Z}$. Then, $\forall k \in \mathbb{Z}$, $\exists x,y \in \mathbb{Z}$ such that $k=mx+ny$.

Therefore, we must have $\gcd(m,n)|k$.

(The part I'm really not sure about) However, $k$ is an arbitrary integer, and thee only integer that is a divisor of any arbitrary integer is $1$.

Thus, $\gcd(m,n)=1$.

Thank you!

Answer 1

Your proof of the first direction looks perfectly fine. Your proof of the second part is definitely on the right track, and as it stands it's not wrong, but it's a little unclear. Somewhat better is to note that, since $\gcd(m,n)$ divides $k$ for every integer $k$, it divides $1$ in particular. Knowing that $\gcd(m,n)$ divides $1$, you get $\gcd(m,n)=1$. That is, you can just immediately take $x$ and $y$ such that $mx+ny=1$ and conclude from there that they are coprime.

Answer 2

You have that, for $k+1\in\mathbb{Z}$ exist $x',y'\in\mathbb{Z}$ such that $mx'+ny'=k+1$ you can use $mx'+ny'-(mx+ny)=k+1-k=1$ thus $m(x'-x)+n(y-y')=1$ then you have $gcd(m,n)=1$.

Answer 3

Your proof of sufficiency was right. Thus, we are going to focus on the part of necessity.

The first thing is that your unsure part is right. It has right logic.

Another proof I am going to give is that, as $m,n\in\mathbb{Z}$, $m\mathbb{Z}+n\mathbb{Z}=gcd(m,n)\mathbb{Z}$.

As $\mathbb{Z}$ is a PID and $m\mathbb{Z}, n\mathbb{Z}$ are ideals, $m\mathbb{Z}+n\mathbb{Z}$ must be a principal ideal, say $d\mathbb{Z}$.

As $m,n\in d\mathbb{Z}$, $d|m$ and $d|n$.

Also, as $d\in d\mathbb{Z}$, $d=mr+ns$, but $\forall e$ such that $e|m, e|n$, $e$ must divide $d$.

Thus $d=gcd(m,n)$.

In this case, you can see that $gcd(m,n)=1$ because $m\mathbb{Z}+n\mathbb{Z}=\mathbb{Z}$.