Can anyone please review/verify this proof of greatest common divisor?

In summary, the greatest common divisor (GCD) of two positive integers divides their least common multiple (LCM). This can be seen by considering that the LCM is essentially a multiplication of unique prime factors, while the GCD is the common prime factors. Therefore, the GCD must exist in the LCM.
  • #1
Math100
756
201
Homework Statement
Prove that the greatest common divisor of two positive integers divides their least common multiple.
Relevant Equations
None.
Proof: Suppose gcd(a, b)=d.
Then we have d##\mid##a and d##\mid##b for some a, b##\in## ##\mathbb{Z}##.
This means a=md and b=nd for some m, n##\in## ##\mathbb{Z}##.
Now we have lcm(a, b)=##\frac{ab}{gcd(a, b)}##
=##\frac{(md)(nd)}{d}##
=dmn
=dk,
where k=mn is an integer.
Thus, d##\mid##lcm(a, b), and so gcd(a, b)##\mid##lcm(a, b).
Therefore, the greatest common divisor of two positive integers divides their least common multiple.
 
Physics news on Phys.org
  • #2
Seems sufficient. Note that the LCM is also basically a multiplication of unique prime factors, for lack of a better phrasing. Take 12 and 28, for example. One is 2*2*3, and the other is 2*2*7. So you end up with 2*2*3*7 as the LCM. The GCD, on the other hand, is prime factors in common, so I this example, 2*2, which are exactly the duplicate factors that get extracted from the LCM, but they must necissarily exist in the LCM.
 
  • Like
Likes Math100
  • #3
valenumr said:
Seems sufficient. Note that the LCM is also basically a multiplication of unique prime factors, for lack of a better phrasing. Take 12 and 28, for example. One is 2*2*3, and the other is 2*2*7. So you end up with 2*2*3*7 as the LCM. The GCD, on the other hand, is prime factors in common, so I this example, 2*2, which are exactly the duplicate factors that get extracted from the LCM, but they must necissarily exist in the LCM.
Thank you for the help.
 

1. What is the purpose of verifying a proof of greatest common divisor?

The purpose of verifying a proof of greatest common divisor is to ensure that the proof is logically sound and free of errors. This helps to establish the validity and reliability of the proof.

2. How do you verify a proof of greatest common divisor?

To verify a proof of greatest common divisor, you need to carefully examine each step of the proof and make sure that it follows the rules of logic. This includes checking for any assumptions, logical fallacies, or errors in reasoning.

3. What are some common mistakes to look out for when reviewing a proof of greatest common divisor?

Some common mistakes to look out for when reviewing a proof of greatest common divisor include incorrect use of mathematical notation, incorrect application of mathematical concepts, and mistakes in logical reasoning.

4. Can a proof of greatest common divisor be verified by someone who is not an expert in mathematics?

Yes, a proof of greatest common divisor can be verified by someone who is not an expert in mathematics as long as they have a basic understanding of mathematical concepts and logical reasoning. However, it is always recommended to have the proof reviewed by an expert in the field.

5. What should be done if errors are found in a proof of greatest common divisor?

If errors are found in a proof of greatest common divisor, the proof should be revised and corrected. It is important to carefully analyze and understand the errors in order to improve the proof and make it more reliable.

Similar threads

  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
883
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
Back
Top