1
$\begingroup$

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)

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

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.