Basic Number Theory: LCM/GCD Proof

In summary, Matt is having difficulty constructing proofs in Number Theory and is unsure of how to proceed. He has been working on this problem for a week and is looking for guidance.
  • #1
Tokipin
19
0
I'm going through the book Number Theory by George E. Andrews. I'm having particular difficulty constructing proofs, which I'm sure is quite common. Problem 4 of section 2-2:

Prove that

[tex]\operatorname{lcm}(a,b) = \frac{{ab}}{{\operatorname{gcd}(a,b)}}[/tex].--------------------
Ok, so I guess a good place to start is the definitions.

gcd( a, b ) is a number d such that:
  • It is a common divisor: d|a and d|b.
  • It is the greatest common divisor: For every c which is a common divisor of a and b, c|d.
lcm( a, b ) is a number m such that:
  • It is a common multiple: a|m and b|m.
  • It is the smallest common multiple.
My proof:
--------------------
1.
First, we show that [itex]\frac{{ab}}{{\operatorname{gcd}(a,b)}}[/itex] is a common multiple of a and b.

We set [itex]a = q_a \operatorname{gcd}(a,b)[/itex] and [itex]b = q_b \operatorname{gcd}(a,b)[/itex] so that [itex]\frac{{ab}}{{\operatorname{gcd}(a,b)}}[/itex] becomes

[tex]\frac{{q_a \gcd (a,b)q_b \gcd (a,b)}}{{\gcd (a,b)}}[/tex]

which is

[tex]q_a q_b \operatorname{gcd}(a,b)[/tex]

which we see:

[tex]a|\bold{q_a \operatorname{gcd}(a,b)} q_b[/tex] and [tex]b|\bold{q_b \operatorname{gcd}(a,b)} q_a[/tex].--------------------
2.
Next, we consider a number f such that a|f and b|f.

We set [itex]f = k_1 a[/itex] and [itex]f = k_2 b[/itex]

which is

[tex]f = k_1 q_a \operatorname{gcd}(a,b)[/tex] and [tex]f = k_2 q_b \operatorname{gcd}(a,b)[/tex].

We set [tex]k_1 q_a \operatorname{gcd}(a,b) = k_2 q_b \operatorname{gcd}(a,b)[/tex]

which becomes

[tex]k_1 q_a = k_2 q_b[/tex]

which we can write as

[tex]\frac{{k_1 }}{{k_2 }} = \frac{{q_b }}{{q_a }}[/tex].

Because [itex]\frac{{q_b }}{{q_a }}[/itex] is irreducible as [itex]q_b[/itex] and [itex]q_a[/itex] are relatively prime since [itex]q_a = \frac{{a}}{{\operatorname{gcd}(a,b)}}[/itex] and [itex]q_b = \frac{{b}}{{\operatorname{gcd}(a,b)}}[/itex], it follows that [itex]k_1 \geqslant q_b[/itex] and [itex]k_2 \geqslant q_a[/itex].

Therefore, [itex]f \geqslant q_a q_b \operatorname{gcd}(a,b)[/itex].--------------------
I'm pretty sure 1 is fine. I'm not really sure about 2. I've been mulling over this problem for about a week as I wanted something fairly solid to show for an attempt before seeking help. Any advice is appreciated.
 
Last edited:
Physics news on Phys.org
  • #2
I want to congratulate you on the care you've taken with this question; it is most pleasing to see someone writing maths so well at such an early stage in their learning.

All that you have is fine, but I'd prefer to say, in the part where you've reached

[tex]k_1 q_a = k_2 q_b[/tex]

for you to simply say that as q_a and q_b are coprime k_1 must divide q_b and k_2 must divide q_a hence... and then for you to complete it without recourse to invoking inequalities.

For instance, all this remains true in the integers rather than the natural numbers, and there are infinitely many numbers smaller than the least common multiple of a and b that are both divisible by a and b (such as -ab).
 
Last edited:
  • #3
Ah, what a breath of fresh air ! I dream of the day that all threads in this forum will look like this.

I can see a brute force proof using prime factorization. But the above method looks a lot more elegant and satisfying.

PS : At most, I might throw in the two lines it takes to show that [itex]q_a, q_b[/itex] are coprime.
 
Last edited:
  • #4
Thank you both for your words. :smile:

A large part of the reason I'm being careful is because I've tried to learn more advanced things and failed. A few pages into Weiss' Algebraic Number Theory and I realized 1) I don't know what a topology is and 2) I don't know what a prime divisor is. :frown: Another example is Karl Rubin's Euler Systems, which I realized a few words in that I wasn't going to get anywhere with. :uhh: It was like trying to read a novel without knowing the alphabet and being blind.

I have many books that I wish I could understand right now because their equations look so beautiful. I am always trying to understand things that are out of my reach. It is only recently that I realized I have to start from the ground and work my way up rigorously. This time around I know how important a strong footing is. And although I am not one for the rigor of axiomatic math, at the very least it ensures my understanding is solid, and that alone is a good enough reason to use it.


-----------------
Matt:

In

[tex]k_1 q_a = k_2 q_b[/tex],

did you mean that since q_a and q_b are coprime, q_a must divide k_2 and q_b must divide k_1? Hence, f is a multiple of [itex]q_a q_b \operatorname{gcd}(a,b)[/itex]. That is quite nicer, since in the positive-only case it takes care of the inequalities implicitly, and it works with all the integers as well. This actually solves another problem from the same chapter where I needed to show that all common multiples of a and b are multiples of lcm(a,b).

I'm a bit confused about the signs. Can a GCD be negative? What about the LCM? My current understanding is that both the GCD and LCM are always positive. What can be negative are the k_1 and k_2 for an arbitrary common multiple f. However, http://en.wikipedia.org/wiki/Gcd says that for any integer m, gcd(ma,mb) = m gcd(a,b), so I guess it can be negative (as when m is -1) unless I misread.
 
  • #5
Well, it looks like you've found an error in wikipedia. It defines gcd to be positive for any pair of integers and indeed states that gcd(ma,mb)=mgcd(a,b) for any integer m. This is indeed not consistent. Of course wikipedia is not infallible. No one is. And no book is infallible (and that is worth rememebering). What is true is that gcd(ma,mb)=|m|gcd(a,b).

Often in maths some things are defined 'up to' something. In number theory, gcd is usaully defined 'up to units'. That is given two objects we can work out a gcd, and if we do it twice we might end up with two answers X and Y, but X will differ by Y only by mutliplication by something invertible (plus or minus 1 in the case of the integers).
 

1. What is the difference between LCM and GCD?

The LCM (Least Common Multiple) of two or more numbers is the smallest positive integer that is divisible by all of the given numbers without leaving a remainder. The GCD (Greatest Common Divisor) of two or more numbers is the largest positive integer that divides all of the given numbers without leaving a remainder.

2. How do you find the LCM and GCD of two numbers?

To find the LCM of two numbers, you can list out the multiples of each number and find the smallest one that is common to both lists. To find the GCD of two numbers, you can list out the factors of each number and find the largest one that is common to both lists. Alternatively, you can use the prime factorization method to find the LCM and GCD more efficiently.

3. What is the relationship between LCM and GCD?

The relationship between LCM and GCD is that the product of the two numbers is equal to the product of their LCM and GCD. In other words, LCM * GCD = a * b, where a and b are the two given numbers.

4. How can you prove that the product of LCM and GCD is equal to the product of the two numbers?

This can be proven using the fundamental theorem of arithmetic, which states that every positive integer can be expressed as a unique product of prime numbers. By writing out the prime factorization of the two numbers and using the properties of exponents and multiplication, the proof can be derived.

5. What are some real-world applications of LCM and GCD?

LCM and GCD are used in various fields such as computer science, engineering, and finance. They are commonly used in programming to optimize algorithms and find the most efficient solutions. In manufacturing, LCM and GCD are used to plan production schedules and determine the least amount of material needed. In finance, LCM and GCD are used to calculate the interest on loans and determine the best payment schedules.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
902
  • Calculus and Beyond Homework Help
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
12
Views
985
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
752
  • Calculus and Beyond Homework Help
Replies
1
Views
820
  • Linear and Abstract Algebra
Replies
8
Views
842
Back
Top