- #1

- 1

- 1

I'm reading through George Andrews'

*Number Theory*at the moment and I spent the last day working on this proof. I wanted to know if anyone could tell me how legitimate my proof is because I was pretty confused by this problem.

The problem is to prove that the least common multiple of two integers a and b is equal to the product of a and b divided by their greatest common divisor. For the sake of typing I'll call the lcm m and the gcd d, as Andrews does. So we're proving m=ab/d.

I thought that the proof would require two parts, the first being to prove that m is divisible by both a and b, which is pretty trivial so I won't type that out.

Part two is what I'm not quite as confident in. Part two, in my reasoning, would be to prove that no smaller integer is divisible by both a and b. I defined a new integer n=m-k, where k is an integer as well. so, n=(ab/d)-k.

For n to be divisible by both a and b, k must be divisible by both a and b, so k must take the form (a^r)(b^s)(x^y), where r, s, x, and y would all be integers, x being positive because if x was negative the number n would come out larger than m and would not serve a purpose in our proof. r and s must both be one, for if they were negative k/a and k/b would not give integers (therefore it would not be divisible by a and b), and they cannot be greater than 1 because if they were, n would become negative (ab/d - a^2b^2, for example). The LCM is by definition positive, so r and s must both be one. So k takes the form ab(x^y).

If that exponent y was positive we would have a number of the form ab or larger, and this will always be larger than ab/d, and thus ab/d - k will come out negative.

If that exponent y was negative, we would have a number of the form ab/x, and any integer solution of this form will come out to be larger than ab/d because d is by definition the largest integer that divides a and b, so x^y would have to be smaller than d and thus ab/x gives an integer larger than ab/d for any applicable x. Thus n becomes negative and cannot be the lcm.

So resolution, any integer smaller than ab/d will either not divide by a and b, or will be negative.

SO (after that long process), m, the lcm, must be equal to ab/d.

Please feel free to criticize, I've been struggling with proofs in number theory will all the abstractions running around.

Thank you!