Thread: If a|c and b|c prove [a,b]|c ([a,b] represents lcm of a and b).

1. If a|c and b|c prove [a,b]|c ([a,b] represents lcm of a and b).

So, I know that c=aq and c=br for some integers q and r. I also know and can prove that c is greater than or equal to d, thus c=dz + t for some integers z and t by Euclid's algorithm. We know that t is greater than or equal to zero and less than d. If we can show d|t, then we know t=0. From here, we have c=dz, thus d|c and by substitution, [a,b]|c and we're done.

The part I don't get is this. How do you show d|t? If I knew how to do this, I could do the rest of the problem.

2. Originally Posted by Geoffrey
So, I know that c=aq and c=br for some integers q and r. I also know and can prove that c is greater than or equal to d, thus c=dz + t for some integers z and t by Euclid's algorithm. We know that t is greater than or equal to zero and less than d. If we can show d|t, then we know t=0. From here, we have c=dz, thus d|c and by substitution, [a,b]|c and we're done.

The part I don't get is this. How do you show d|t? If I knew how to do this, I could do the rest of the problem.
If I were doing this I would consider the prime decomposition of a, b, c and [ab].

RonL

3. Yes, but I'm not allowed to assume that, so I have to be creative. I could use it if I proved every number has a prime decomposition though, and then use that to prove my theorem, but I don't know how to do that.

4. Okay, I'm stuck. If you all have time, please show me how to prove: if a|c and b|c then [a,b]|c.

5. Is it clear to you that gcd(a,b)|c?
Now lcm(a,b)*gcd(a,b)=ab| $c^2$.
From the above is it possible to conclude that gcd(a,b)|c?

6. Plato, I am not allowed to assume what you just suggested. Indeed, the next problem is this: Prove lcm(a,b) x gcd(a,b) = ab

7. Originally Posted by Geoffrey
Plato, I am not allowed to assume what you just suggested. Indeed, the next problem is this: Prove lcm(a,b) x gcd(a,b) = ab
Say,
$a,b>0$.

Let, $d=\gcd(a,b)$
And we can define a positive integer,
$m=\frac{ab}{d}$.
Let, $c$ be a common multiple of $a,b$.
We need to show,
$m\leq c$
Note,*)
$\frac{c}{m}=\frac{cd}{md}=\frac{c(ax+by)}{ab}=\fra c{c}{b}\cdot x+\frac{c}{a}\cdot y$
Where,
$\frac{c}{b},\frac{c}{a} \in \mathbb{Z}^+$ because it is a common multiple.
Thus, $m|c$.
That means,
$m\leq c$.
Thus,
$\mbox{lcm}(a,b)=m$
Thus,
$\gcd(a,b)\mbox{lcm}(a,b)=ab$.

*)Using the fudamental property of greatest common divisors,
$\gcd(a,b)=ax+by$

Okay, I follow your proof so far, and it all makes sense, but exactly how does it prove that if a|c and b|c, then lcm(a,b)|c? I'm sure the answer is pretty obvious, but I'm just having trouble seeing it.

9. Originally Posted by Geoffrey
Okay, I follow your proof so far, and it all makes sense, but exactly how does it prove that if a|c and b|c, then lcm(a,b)|c? I'm sure the answer is pretty obvious, but I'm just having trouble seeing it.
$a|c$
$c = x\cdot a$, where $x\ \epsilon\ N$

$b|c$
$b|x\cdot a$
Divide both sides by $gcd(a,\ b)$
$\frac{b}{gcd(a,\ b)}|x\cdot \frac{a}{gcd(a,\ b)}$
But $gcd\left(\frac{b}{gcd(a,\ b)},\ \frac{a}{gcd(a,\ b)}\right)\ =\ 1$
$\frac{b}{gcd(a,\ b)}|x$

$\frac{a\cdot b}{gcd(a,\ b)}|x\cdot a$

$lcm(a,\ b)|c$

This looks similar to the Chinese remainder theorem.

10. I just found out that I am not allowed to work with numbers like (a/b). I must only work in integers, and cannot express them as fractions. My teacher will only let me use the multiplication, addition, and subtraction operators. Your proofs are helpful, but I have no clue how to express them without using division. (Oh, divides | is okay. | is acceptable)

11. $a|c\ \Rightarrow\ c\ =\ x\cdot a$

$b|c\ \Rightarrow\ b|x\cdot a$

$b|x\cdot gcd(a,\ b)$

$a\cdot b|x\cdot a\cdot gcd(a,\ b)$

$a\cdot b|c\cdot gcd(a,\ b)$

$lcm(a,\ b)|c$