Question

13. The least common multiple of two non-zero integers a and b is the unique positive integer m such that (i) m is a common multiple, i.e. a divides m and b divides m, (ii) m is less than any other common multiple: We denote the least common multiple of a and b by [a, b] or 1cm[a, b], Give a proof by contradiction that if a positive integer n is a common multiple of a and b then [a, b] divides n. [Use the division theorem. If [a, b] does not divide n then n = [a, b]q + r where 0 < r < [a, b]. Now prove that r is a common multiple of a and b.} This means that ab/[a,b] is an integer. Prove that this integer is a common divisor of a and b. Deduce that ab/[a, b] (a, b), t

Answer 1

Answer:

[a,b] divides n

Step-by-step explanation:

Let us denote the least common multiple of a and b [a,b]=m.

We want to prove that m divides n, where n is a multiple of a and b.

We suppose m does not divide n, then by the Division Theorem, there exists q and r integers such that:

(1) ... n=mq+r, where 0<r<m

As n is a multiple of a and b, there exists s and t integers such that:

sa=n and tb=n

Same thing happens to m as it is the least common multiple, there exists u and v such that:

ua=m and vb=m

So (1) has the following form:

n=mq+r ⇒ sa=uaq+r ⇒sa-uaq=r⇒(s-uq)a=r and

n=mq+r ⇒ tb=vbq+r ⇒ tb-vbq=r⇒ (t-vq)b=r

So r is a multiple of a and b, but r<m which is a contradiction as, m is the least common multiple of a and b. So this concludes the proof.

So this means that $\frac{ab}{m}$ is and integer.

As m= vb, then $\frac{m}{b}$ is an integer, lets say $\frac{m}{b}$=v; and as m=ua, then $\frac{m}{a}$=u.

So $\frac{ab}{m}$v=$\frac{ab}{m}$$\frac{m}{b}$=a, so $\frac{ab}{m}$ divides a; on the other hand, $\frac{ab}{m}$u=$\frac{ab}{m}$$\frac{m}{a}$=b, so $\frac{ab}{m}$ divides b. From this we can conclude that $\frac{ab}{m}$ is a common divisor of a and b.