# 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|$\displaystyle 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,
$\displaystyle a,b>0$.

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

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

8. Not only it proves this, it answers your other question.
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.
$\displaystyle a|c$
$\displaystyle c = x\cdot a$, where $\displaystyle x\ \epsilon\ N$

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

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

$\displaystyle 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. $\displaystyle a|c\ \Rightarrow\ c\ =\ x\cdot a$

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

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

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

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

$\displaystyle lcm(a,\ b)|c$

#### Search Tags

a|c, b|c, lcm, prove, represents 