If $x$ is any common multiple of $a_1, a_2 \cdots a_n$ all $\neq 0$ then prove that $[a_1, a_2,\ldots,a_n]$ divides $x$. Note, $[a_1, a_2,\ldots,a_n]$ is LCM.

The solution provided in my text:

Let $[a_1, a_2,\ldots,a_n] = a$

We write $x = aq + r$ with $q, r$ being integers and $0 \leq r < a$

Now $a_i$ divides $x$ and $a$ for each $i$. This means that $a_i$ divides $x - aq = r$. But $0 \leq r < a$ implying that $r = 0$. Therefore $a | x$.

My question

I follow the proof everywhere except where it is said that if $a_i | r$ and $r < a$ then $r = 0$. Wouldn't this be true only if $ r < a_i \leq a$? Otherwise we don't have a guarantee that $r$ isn't $> a_i$. Or is this not possible in the first place? Am I missing something?

  • $\begingroup$ Since $a_i$ divides $r$ for each $i$, it follows that the LCM of $a_i$, that is $a$, divides $r$. Since $0 \leq r < a$, it follows that $r=0$. The only number less than $a$ and is divisible by $a$ is 0. $\endgroup$ – user348749 Jul 11 '16 at 4:28
  • $\begingroup$ You know that r is a common multiple of the $a_i$ which is less than the least common multiple. $\endgroup$ – user84413 Jul 11 '16 at 4:33
  • $\begingroup$ It just prove r was a common multiple that is less than the least common multiple. So r =0. $\endgroup$ – fleablood Jul 11 '16 at 6:12

By definition, $a$ is the least common multiple of the $a_i$. That is, there is no smaller positive integer that is a multiple of every $a_i$. We know that $r$ is smaller than $a$ and divisible by every $a_i$, so it can't be positive.

  • $\begingroup$ Oh so basically because $a$ is the LCM, the only value that $r$ can take is $0$ since each $a_i$ divides $r$, implying that $r$ is a common multiple? $\endgroup$ – Airdish Jul 11 '16 at 5:46
  • $\begingroup$ Exactly. Since $r$ is a common multiple, it can't be smaller than the least common multiple unless it's $0$. $\endgroup$ – Eric Wofsey Jul 11 '16 at 5:49
  • $\begingroup$ Thanks a lot. I'll have to be wary of these underlying facts from now on... $\endgroup$ – Airdish Jul 11 '16 at 5:50
  • 1
    $\begingroup$ Yeah, it's like about the single a_i but all of them. It could have been better worded. $\endgroup$ – fleablood Jul 11 '16 at 6:13

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.