Answered

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 :

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 [tex]\frac{ab}{m}[/tex] is and integer.

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

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

Other Questions