Let m be theleast common multipleof a and b, and let c be aof a and b. Show that m divides c. Hint: use the division theorem on m and c , and show that the remainder r is a common multiple of a and b, hence r=0.common multiple

Printable View

- Sep 14th 2009, 06:50 PMpeng783division theorem
Let m be the

**least common multiple**of a and b, and let c be aof a and b. Show that m divides c. Hint: use the division theorem on m and c , and show that the remainder r is a common multiple of a and b, hence r=0.__common multiple__ - Sep 18th 2009, 10:34 AMpeng783
m is the LCM of a and b, so a|m, b|m

c is a CM of a and b, so a|c, b|c

m<=c, since m is the LCM.

so, use the division theorem we set up the equation c=mq+r. for some integers q and r, where 0<=r<m.

Rearrange the equation which becomes r=c-mq.

since a|c, a|m, b|c, b|m, we get a|r, b|r.

We know m is the LCM, so r should be 0, otherwise m will not be the LCM.

since r = 0, we get c=mq, which completes the proof m|c.