Is this proof of the least common multiple theorem in number theory valid?

In summary: First, let l be the smallest integer that divides both a and b, and write a=lA and b=lB. Then k=ln for some integer n. Now n must be divisible by both A and B: indeed, if p is any prime that divides l, it cannot divide both A and B, for then l would not be the smallest integer with this property. Therefore n is divisible by the product of all such primes, which is the greatest common divisor of A and B.
  • #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!
 
Mathematics news on Phys.org
  • #2
River Robles said:
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.
River Robles said:
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 to Is this proof of the least common multiple theorem in number theory valid?

1. What is Number Theory?

Number Theory is a branch of mathematics that deals with the properties and relationships of numbers, particularly integers.

2. What are the main concepts in Number Theory?

The main concepts in Number Theory include prime numbers, divisibility, congruence, and Diophantine equations.

3. What is the significance of prime numbers in Number Theory?

Prime numbers are important in Number Theory because they are the building blocks of all other integers and have unique properties that are crucial in many mathematical applications.

4. How is Number Theory used in cryptography?

Number Theory plays a key role in cryptography, particularly in the development of algorithms for secure communication and data encryption. Prime numbers and modular arithmetic are used to create encryption keys and ensure secure communication.

5. Can Number Theory be applied in real-life situations?

Yes, Number Theory has various practical applications in fields such as computer science, engineering, and physics. It is used to solve real-world problems involving data encryption, coding theory, and algorithms for efficient computation.

Similar threads

  • General Math
Replies
1
Views
1K
Replies
15
Views
1K
Replies
1
Views
949
  • General Math
Replies
1
Views
2K
  • General Math
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
Replies
1
Views
1K
Replies
4
Views
859
  • General Math
Replies
8
Views
2K
Back
Top