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

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)

• $$ms + nt = 1$$ Multiply both sides by $x$ and look at terms on left hand side – AgentS Oct 6 '14 at 14:15

$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$

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

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

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. 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}$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\$.