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
    2016 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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted

Similar Discussions: Question in Number Theory
  1. Number Theory (Replies: 7)

  2. Number theory (Replies: 2)

  3. Number Theory (Replies: 1)

  4. Number Theory (Replies: 2)