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?

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

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

| cite | improve this answer | |

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).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.