# Prove if If $m \in Z^+$, $a|m$, and $b|m$, then $\mbox{lcm}(a,b) \leq m$.

Let $a,b \in Z^+$. Define $\mbox{lcm}(a,b) := \frac{ab}{\gcd(a,b)}$. Prove that $\mbox{lcm}(a,b)$ is the smallest (positive) integer that is evenly divisible by both $a$ and $b$.

I am trying to prove this using 3 conditions. I have proved the first two so far (and wrote their proofs below) but I am unsure how to prove the 3rd point.

1) $\mbox{lcm}(a,b) \in Z^+$,

2) $a| \mbox{lcm}(a,b)$ and $b|\mbox{lcm}(a,b)$, and

3) If $m \in Z^+$, $a|m$, and $b|m$, then $\mbox{lcm}(a,b) \leq m$

1) $\mbox{lcm}(a,b) \in Z^+$

It was stated that the least common multiple of $a,b$ was defined to be $\mbox{lcm}(a,b) := \frac{ab}{\gcd(a,b)}$. We know that $a, b \in \mathbb{Z^+}$, and that $gcd(a,b) \in \mathbb{Z}$, based on the definition of the greatest common denominator.

Also from the definition of the $gcd$, we know that it divides both $a$ and $b$. For this reason, we know that $\frac{ab}{\gcd(a,b)} \in \mathbb{Z}$. This is because when simplified, the denominator will cancel, and then whatever is remaining in the numerator can be written over $1$, which allows us to conclude it is an integer. Thus we have proved $\mbox{lcm}(a,b) \in Z^+$.

2) $a| \mbox{lcm}(a,b)$ and $b|\mbox{lcm}(a,b)$

As stated before, $\mbox{lcm}(a,b) := \frac{ab}{\gcd(a,b)}$. We also know that if $a|\mbox{lcm}(a,b)$ and $b|\mbox{lcm}(a,b)$, then $a \cdot k = \mbox{lcm}(a,b)$ for some $k \in Z$, and also that $b \cdot j = \mbox{lcm}(a,b)$ for some $j \in Z$.

Looking at the equation stated for $lcm$, we can say that the '$k$' to make $a| \mbox{lcm}(a,b)$ true is $\dfrac{b}{gcd(a,b)}$, and the '$j$' to make $b|\mbox{lcm}(a,b)$ true is $\dfrac{a}{gcd(a,b)}$. Clearly since there exists values to make these claims true, we can conclude that $a| \mbox{lcm}(a,b)$ and $b|\mbox{lcm}(a,b)$.

3) If $m \in Z^+$, $a|m$, and $b|m$, then $\mbox{lcm}(a,b) \leq m$

??

• What a strange definition of lcm...
– lhf
Oct 22 '15 at 1:20
• The usual way to do these things is, I believe, to deal with the case when $a,b$ are coprime first. Then you can use the fact that if a number is divisible by two coprime numbers, it is divisible by their product. It really depends on what sort of tools you're allowed to use. Oct 22 '15 at 1:29
• $a,b\mid m\iff \text{lcm}(a,b)\mid m\implies \text{lcm}(a,b)\le m$. Oct 22 '15 at 2:41

Let $d=\gcd(a,b)$, and let $a=da_1$ and $b=db_1$. Note that $a_1$ and $b_1$ are relatively prime and that $\frac{ab}{\gcd(a,b)}=da_1b_1$.
It is clear that $da_1b_1$ is divisible by $a$ and $b$. We show no smaller positive integer is divisible by $a$ and $b$.
Suppose that $m$ is divisible by $a$ and $b$. Let $m=am_1=da_1m_1$. Since $m$ is divisible by $b$, $db_1$ divides $da_1m_1$, so $b_1$ divides $a_1m_1$. But $a_1$ and $b_1$ are relatively prime, so $b_1$ divides $m_1$, say $m_1=b_1m_2$.
Then $m=da_1m_1=da_1b_1m_2$, and therefore $da_1b_1$ divides $m$. This completes the proof.