The Problem

Let $\mathcal{J}_m$ be the set of all integral multiples of the integer $m$. Prove that \begin{equation*} \mathcal{J}_m\cap\mathcal{J}_n=\mathcal{J}_{\operatorname{lcm}(m,n)}. \end{equation*}

Previous Attempt at a Solution

This is a problem that I am redoing. The solution I first submitted was marked as wrong. Here is what I originally had...

Proof. First let $\mathcal{J}_m=\left\lbrace mp\mid p\in\mathbb{Z}\right\rbrace$ and $\mathcal{J}_n=\left\lbrace nq\mid q\in\mathbb{Z}\right\rbrace$, for an integer $m$ and an integer $n$. The intersection of these two sets will contain all elements shared in common between the two, such that $mp=nq$. In general, the least common multiple of two integers is the smallest positive integer $r$ that is divisible by those two integers, in this case $m$ and $n$. In other words, we can say that for two integers $m$ and $n$, there exists a least common multiple $r$, such that $mj=r$ and $nk=r$ for some integers $j$ and $k$, since $\mathcal{J}_m$ is the set of all integer multiples of $m$ and $\mathcal{J}_n$ the set of all integer multiples of $n$. This implies that $mj=nk$ when $mj=r$ and $nk=r$. From this, we can see that $\mathcal{J}_m\cap\mathcal{J}_n$ will then consist of all these values $r_1,r_2,r_3,\ldots,r_n$ such that $mp_n=nq_n=r_n$ for all $n,$ which is the same as all of the least common multiples of $m$ and $n$. Thus, $\mathcal{J}_m\cap\mathcal{J}_n=\mathcal{J}_{\operatorname{lcm}(m,n)}.$



So there is clearly a great deal that is incorrect with my original solution. I'd like to restart from scratch, because I feel like what I put isn't even salvageable. So my questions are...

  1. How should I start this problem?
  2. How/where does the least common multiple bit come into play?
  3. Was there anything I did right?

Other Details

The book I am using is Number Theory by Andrews. This is my first exposure to the subject, and the placement of the exercise doesn't assume you know much. In fact, all we covered up to the exercise in question is divisibility, Euclid's division lemma, and induction. I am not necessarily limited to those three things, but I just wanted to give you an idea where the problem is in context of the book.

Thank you all in advance for your help.


First of all, $+1$ for a model question.

Second, your question itself!

How should I start?

Well, first of all, equality of two sets $A$ and $B$ happens if and only if $A \subseteq B$ and $B \subseteq A$. So this should be your aim. What you can do to clear your head now, is to translate this in words, where $A = \mathcal J_m \cap \mathcal J_n$ and $B = \mathcal J_{\operatorname{lcm} (m,n)}$:

$A \subset B$ means : every number that is a multiple of $m$ and $n$, is also a multiple of $\operatorname{lcm}(m,n)$. $B \subset A$ means : every number that is a multiple of $\operatorname{lcm}(m,n)$, is also a multiple of $m$, and a multiple of $n$.

Suddenly ,the problem may look a whole lot easier, and you can probably say the proof in words. But, writing is important, so it's best we do it.

Was there anything I did right?

Certainly, you stated the definitions of $\mathcal J_m$ and $\mathcal J_n$ correctly. You also mentioned the definition of $\operatorname {lcm}$ correctly. So you've got the ideas. All you need to do is to create that well oiled machine that hammers the proof home, and convinces the non-believers.

How to write the proof?

To show that $A \subset B$, let $x \in A$. Then, $x \in \mathcal J_m$ and $x \in \mathcal J_n$, so $x$ is a common multiple of $m$ and $n$. So, $x \geq \operatorname{lcm} (m,n)$ is true. However, we want to show that $x$ is a multiple of the $\operatorname{lcm}$. How would we do this?

Well, we can use the division algorithm. By that, $x = q \times \operatorname{lcm} (m,n) + r$, where $0 \leq r < \operatorname{lcm}(m,n)$. Then, $r = x - q \times \operatorname{lcm}(m,n)$

Can you see why $r$ is also a common multiple of $m,n$? But then, it's been chosen smaller then the $\operatorname{lcm}$!

Hence, it's only possible that $r=0$, so that $x$ is a multiple of the $\operatorname{lcm}$. Hence, $x \in B$, so $A \subset B$.

The other way is much easier : if $x \in B$, then $x$ is a multiple of $\operatorname{lcm} (m,n)$, hence a multiple of $m$ and $n$ individually, hence in $A$.

This way, we get $A=B$, completing the proof.

Please ask if there are further doubts. The use of the division algorithm is a very standard one in these scenarios.


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.