1
$\begingroup$

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$

??

$\endgroup$
  • 1
    $\begingroup$ What a strange definition of lcm... $\endgroup$ – lhf Oct 22 '15 at 1:20
  • 1
    $\begingroup$ 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. $\endgroup$ – tomasz Oct 22 '15 at 1:29
  • $\begingroup$ $a,b\mid m\iff \text{lcm}(a,b)\mid m\implies \text{lcm}(a,b)\le m$. $\endgroup$ – user236182 Oct 22 '15 at 2:41
1
$\begingroup$

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.

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