1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Question in Number Theory

  1. Jun 30, 2016 #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!
  2. jcsd
  3. Jun 30, 2016 #2


    User Avatar
    2017 Award

    Staff: Mentor

    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.
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted