Proving De Morgan's Laws for GCD and LCM: A Natural Number Proof

  • Thread starter aufbau86
  • Start date
  • Tags
    Gcd Proof
In summary, the conversation discusses the concepts of greatest common divisor (gcd) and lowest common multiple (lcm) in a system where n is a natural number and S is the set of all natural numbers that divide n. The conversation also introduces the notation x' for n/x. The question at hand is whether de Morgan's laws hold for this system, specifically if (a /\ b)' = a' \/ b' is true. The conversation concludes with requesting help in proving this statement.
  • #1
aufbau86
2
0
Let n be a natural number, and let S be the set of all natural numbers that
divide n.

For a, ,b in S, let gcd(a, b) = a /\ b and lcm(a, b) = a \/ b. For each x
in S, let x' denote n/x. Do de Morgan's laws hold for this system?

(gcd = greatest common divisor, lcm = lowest common multiple)

This is what I have so far for wanting to show (a /\ b)' = a' \/ b'

lcm(n/a, n/b) = a' \/ b'

d = gcd(a, b) = a /\ b.

d' = n/d

So somehow I need to show that n/gcd(a, b) = lcm(n/a, n/b)

From here I've only hit dead-ends.
 
Physics news on Phys.org
  • #2
I'm not sure how to proceed in order to show that de Morgan's laws hold for this system. Any help would be greatly appreciated. Thanks!
 

What is the concept of gcd and lcm in mathematics?

The greatest common divisor (gcd) and least common multiple (lcm) are fundamental concepts in mathematics that are used to find the largest and smallest common factors of two or more numbers, respectively. They are important in many areas of mathematics, such as number theory, algebra, and cryptography.

What is the proof for gcd and lcm?

There are several different proofs for gcd and lcm, depending on the context in which they are being used. However, a common proof for both concepts involves using prime factorization to show that the gcd and lcm can be expressed as a product of prime numbers.

What is the relationship between gcd and lcm?

The gcd and lcm are related in that the gcd is the largest number that divides both of the given numbers, while the lcm is the smallest number that is divisible by both numbers. In other words, the gcd is a factor of the lcm.

How do I find the gcd and lcm of multiple numbers?

To find the gcd and lcm of multiple numbers, you can use a variety of methods, such as listing out the factors and finding the greatest common factor, or using the prime factorization method. There are also algorithms, such as the Euclidean algorithm, that can be used to find the gcd and lcm of multiple numbers efficiently.

Why are gcd and lcm important in real-world applications?

Gcd and lcm have several practical applications, such as in simplifying fractions, finding equivalent ratios, and solving problems related to time and distance. They are also used in computer science, particularly in cryptography and data compression algorithms.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
964
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
932
  • Calculus and Beyond Homework Help
Replies
1
Views
511
  • Calculus and Beyond Homework Help
Replies
3
Views
524
  • Calculus and Beyond Homework Help
Replies
3
Views
696
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
522
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
462
Back
Top