Prove that if $\gcd (m,n)=1$ and $m\mid x$ and $n\mid x$, then $mn\mid x$.

Question

I've come across the statement that if $\gcd (m,n)=1$ and $m\mid x$ and $n\mid x$, then $mn\mid x$. (This is needed for a proof of the correctness of RSA that I have been given.)

I can't see how to prove that is the case. Can anyone either show me how, or give me a clue?

(NB: gcd = greatest common divisor = highest common factor = hcf)

Answer 1

$x=k\cdot m$ and $n$ divides $k\cdot m$.
From Euclid's lemma $n\mid k$ so $k=c\cdot n$
Replacing we have $x=c\cdot n \cdot m$

Answer 2

From the definition of L.C.M., $m|x, n|x$ implies L.C.M.of ${m,n}$ divides $x$. If $(m,n)=1$ then their L.C.M is $mn$.

Answer 3

Solve $mu+nv=1$ then multiply by $x$.

So $mxu+nxv=x$.

But $n\mid x$ means $mn\mid mx\mid mxu$ and $m\mid x$ means $mn\mid xn\mid xnv$. So $mn\mid (mxu+nxv)=x$.

Answer 4

Hint using ring theory:

$m\mathbb{Z}$$\cap$ $n\mathbb{Z}$ $=$ $lcm(m,n)\mathbb{Z}$ where $m\mathbb{Z}$ denotes ideal of $\mathbb{Z}$ generated by $m$.

Answer 5

From Bezout's identity, $\gcd(m,n) = 1$ implies that there exist integer $a$ and $b$ where $am + bn = 1$. $m|x$ means there exists integer c such that $cm = x$, and likewise $dn = x$.

$$\begin{align} && am + bn = 1\\ \Rightarrow && amx + bnx = x\\ \iff && am(dn) + bn(cm) = x\\ \iff && (ad + bc)mn = x\\ \Rightarrow &&mn | x \end{align}$$

Answer 6

Since $\Bbb Z$ is a Euclidean domain, least common multiples (common multiples that divide all other common multiples) always exist there. Also $\gcd(m,n)=1$ implies that no proper divisor $d$ of $mn$ is common multiple of $m,n$ (if it were, $\frac{mn}q$ would be common divisor of $m,n$). Now $m\mid x$ and $n\mid x$ (i.e., $x$ is a common multiple of $m,n$) together imply that $x$ is a multiple of (the least common multiple) $mn$.