# A proof I'm not sure of: Let $n,m$ be coprime so that $x|m$, $y|n$. Prove $(x,y)=1$

Let $n,m$ be coprime so that $x|m$, $y|n$, $x,y \in \mathbb Z$. Prove $(x,y)=1$

This proof was shown in class, and I'm not certain of the last step:

$x|m$, $y|n$ so there are $a,b \in \mathbb Z$ so that $m=ax$ and $n=by$.

We know $(m,n)=1$ so there are $s,t \in \mathbb Z$ so that $$sn+tm=1 \\s(ax)+t(by)=1 \\(sa)x+(tb)y=1$$

Lets say $p=sa$, $q=tb$ so we get: $$px+qy=1$$

Therefore $(x,y)=1$.

Why is the last step true? The claim that if d=$(x,y)$ then there are integers $c,e$ so that $d=cx+ey$ isn't true bothways, is it?

• if $d=(x,y) > 1$, that would mean $d(\frac{x}{d}+q\frac{y}{d})=1$, implying $d| 1$, so $d=1$ – r9m Mar 8 '14 at 16:26

## 2 Answers

By Bezout's Lemma: $\exists a,b$ s.t. $ax+by=1$ if and only if $gcd(x,y)=1$.

Hint $\,\ d\mid x,y\,\Rightarrow\, d\mid ax+by = 1.\,$ Yours is the special case $\,d=(x,y).$

Remark $\$ There is no need to use Bezout's Lemma for any of this since, more generally

$$\begin{eqnarray} &&d\mid x\mid m\\ &&d\mid y\mid n\end{eqnarray}\,\Rightarrow\, d\mid (m,n)$$

Hence, for $\,d = (x,y)$

$$\begin{eqnarray}&&x\mid m\\ &&y\mid n\end{eqnarray}\,\Rightarrow\, (x,y)\mid (m,n)$$

Yours is the special case $\,(m,n)=1.\,$ The above proof works in any domain where gcds exist (generally such domains do not enjoy a linear Bezout representation for the gcd).