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

• Dec 7th 2006, 02:26 PM
Geoffrey
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.
• Dec 7th 2006, 02:53 PM
CaptainBlack
Quote:

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
• Dec 7th 2006, 02:59 PM
Geoffrey
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.
• Dec 7th 2006, 03:30 PM
Geoffrey
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.
• Dec 7th 2006, 04:20 PM
Plato
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?
• Dec 8th 2006, 07:48 AM
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
• Dec 8th 2006, 08:08 AM
ThePerfectHacker
Quote:

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$
• Dec 8th 2006, 11:52 AM
Geoffrey
Quote:

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.
• Dec 8th 2006, 02:11 PM
TriKri
Quote:

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.
• Dec 8th 2006, 02:20 PM
Geoffrey
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)
• Dec 8th 2006, 02:32 PM
TriKri
$\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$