2

Prove: If $a,b,c$ in $\mathbb N$, then $lcm(ca, cb) = c \cdot lcm(a,b)$.

Assume $a$,$b$,$c \in \mathbb N$. Let $m = lcm(ca,cb)$ and $n = c\cdot lcm$. Showing $n = m$. Since $lcm(a,b)$ is a multiple of both a and b, then by definition $lcm(a,b) = ax = by$ for some $x,y \in Z$. This means that $m = lcm(ca,cb) = cax = cby$. Likewise $n = c \cdot lcm(a,b) = cax = cby$. Therefore $n = m$. Thus $lcm(ca, cb) = c \cdot lcm(a,b)$.

Is this a valid proof, being able to show that $n$ and $m$ are equal in this way, and if not, why not? The book i got this problem from was http://www.people.vcu.edu/~rhammack/BookOfProof/BookOfProof.pdf on page 106. The author uses this proof problem as a way to show how to prove using $m \le n$ and $n \le m$ making them indirectly equal to each other, but it seemed to me that this particular example could be proved more simply by being directly equaled. Is this reasoning correct?

Alan
  • 16,582
alan
  • 525
  • $m=\text{lcm}(ca,cb) = cax'=cby'$. To go this route, you need to show $x=x'$ and $y=y'$. – David P Jul 26 '16 at 03:26
  • @DavidP ah, this comment alone answered something critical that i did not understand, that each lcm equations x and y could be different and that part must be proven separately. Thank you. – alan Jul 26 '16 at 04:37

2 Answers2

5

Your proof isn't valid. At this step

This means that $m=lcm(ca,cb)=cax=cby$

you're using the proposition to prove itself. Breaking it down a bit more, we have:

$lcm(a,b)=ax=by$

implies

$c \cdot lcm(a,b)=cax=cby$

And then you're going from there to:

$c \cdot lcm(a,b) = lcm(ca, cb) = cax = cby$

but that is what you're trying to prove!

Bill
  • 166
  • ah, is that why it must be proven using $n \le m$ and $m \le n$? – alan Jul 26 '16 at 03:36
  • I mean, I don't know if I'd want to say it must be proven that way. There may very well be other valid ways to prove it. But proving $n \leq m$ and $m \leq n$ is not an uncommon way of proving equality, and I think it works quite nicely here. – Bill Jul 26 '16 at 03:55
3

Use the fact that: $gcd(a,b)lcm(a,b)=ab$

Also $gcd(ca,cb)=c*gcd(a,b)$

$lcm(ca,cb)={{(ca)(cb)}\over{gcd(ca,cb)}}={{(ca)(cb)}\over{c*gcd(a,b)}}=c*{{ab}\over{gcd(a,b)}}=c*lcm(a,b)$

-or-

Just that $lcm(ca,cb)$ consists of all prime factors in $ca$ and $cb$ to the highest/maximal power of the $2$ and so $c$ can be factored out as it contributes the same to those prime factors in each number.

miniparser
  • 1,197
  • i was more looking for why my method was perhaps not valid with an explanation as to why. But thank you for giving two new methods of proof. I am obviously new to them so seeing these extra ways is helpful. – alan Jul 26 '16 at 04:39