- #1
River Robles
- 1
- 1
Hello
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!
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!