# $a_i \mid r$ implies that $r = 0$ if $0 \leq r < a$?

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?

• 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. – user348749 Jul 11 '16 at 4:28
• You know that r is a common multiple of the $a_i$ which is less than the least common multiple. – user84413 Jul 11 '16 at 4:33
• It just prove r was a common multiple that is less than the least common multiple. So r =0. – 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.
• 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? – Airdish Jul 11 '16 at 5:46
• Exactly. Since $r$ is a common multiple, it can't be smaller than the least common multiple unless it's $0$. – Eric Wofsey Jul 11 '16 at 5:49