Question in Number Theory

  • #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!

Answers and Replies

  • #2
So we're proving m=ab/d.
Based on what you show afterwards, you seem to use this as definition for m, and then prove that m is the least common multiple.
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
If you allow null that expression is trivial, because you can always set r=s=0, y=1, x=k. Which does not satisfy the conditions you want to put on the expression later. If you allow negative exponents then your argument gets circular as x^y gets exactly the 1/d factor you started with.

There is a much better way to express k.

Related Threads on Question in Number Theory