The GCD and LCM describe two different but closely related properties of a pair of positive integers. The GCD is the greatest positive integer that divides both numbers, while the LCM is the smallest positive integer divisible by both. For any two positive integers, the product of their GCD and LCM equals the product of the two original integers. This relationship provides an efficient method for calculating the LCM when the GCD is known, or the GCD when the LCM is known. The relationship can also be understood through prime factorization: the GCD uses the smallest exponents of common prime factors, while the LCM uses the greatest exponents of all prime factors.
Relationship Between GCD and LCM
The greatest common divisor and least common multiple of two positive integers are connected through a fundamental mathematical relationship. Their product equals the product of the original integers.
| Name | Expression | Description |
|---|---|---|
Fundamental GCD-LCM Relationship | GCD(a,b) × LCM(a,b) = a × b | For two positive integers, the product of their GCD and LCM equals the product of the integers. |
Calculating LCM | LCM(a,b) = (a × b)/GCD(a,b) | The LCM is obtained by dividing the product of the original integers by their GCD. |
Calculating GCD | GCD(a,b) = (a × b)/LCM(a,b) | The GCD is obtained by dividing the product of the original integers by their LCM. |
Coprime Integers | If GCD(a,b) = 1, then LCM(a,b) = a × b | The LCM of two coprime positive integers equals their product. |
Explanation
Variables
| Symbol | Meaning |
|---|---|
a | The first positive integer. |
b | The second positive integer. |
GCD(a,b) | The greatest common divisor of a and b. |
LCM(a,b) | The least common multiple of a and b. |
p | A prime factor used when analyzing the relationship through prime factorization. |
Example or application
A worked example has not yet been added.
Definition
For any two positive integers a and b, the product of their greatest common divisor and least common multiple equals the product of a and b.
Purpose
This relationship provides a direct way to calculate GCD or LCM when the other value and the original integers are known.
Importance
It connects two central number theory concepts and simplifies calculations involving divisibility, prime factorization, fractions and numerical relationships.
Key Concepts
| Name | Description |
|---|---|
Greatest Common Divisor | The largest positive integer that divides both given integers exactly. |
Least Common Multiple | The smallest positive integer divisible by both given integers. |
Product Relationship | The product of GCD and LCM equals the product of the original two positive integers. |
Prime Exponent Comparison | The GCD uses minimum exponents of shared primes, while the LCM uses maximum exponents. |
Coprime Integers | When two positive integers have a GCD of 1, their LCM equals their product. |
Characteristics
The relationship applies to any two positive integers.
The product of GCD and LCM equals the product of the original integers.
The GCD cannot exceed the smaller input integer.
The LCM cannot be smaller than the larger input integer.
Prime factorization provides a way to understand the relationship.
The GCD uses the minimum exponents of common prime factors.
The LCM uses the maximum exponents of all prime factors.
For coprime integers, the GCD is 1 and the LCM is their product.
Types
| Name | Description |
|---|---|
GCD from LCM | Calculating the greatest common divisor when the LCM and original integers are known. |
LCM from GCD | Calculating the least common multiple when the GCD and original integers are known. |
Prime Factorization Relationship | Understanding GCD and LCM through minimum and maximum prime exponents. |
Coprime Number Relationship | Using the fact that the GCD of coprime integers is 1. |
Components
| Name | Description |
|---|---|
First Integer | The first positive integer in the relationship. |
Second Integer | The second positive integer in the relationship. |
GCD | The greatest common divisor of the two integers. |
LCM | The least common multiple of the two integers. |
Product | The multiplication of the original integers or the GCD and LCM. |
Properties
| Name | Expression | Description |
|---|---|---|
Product Identity | GCD(a,b) × LCM(a,b) = ab | The product of the GCD and LCM equals the product of the original positive integers. |
LCM from GCD | LCM(a,b) = ab/GCD(a,b) | The LCM can be found directly when the GCD and original integers are known. |
GCD from LCM | GCD(a,b) = ab/LCM(a,b) | The GCD can be calculated when the LCM and original integers are known. |
Coprime Integers | GCD(a,b) = 1 ⇒ LCM(a,b) = ab | For coprime positive integers, the LCM equals their product. |
Equal Integers | GCD(a,a) = LCM(a,a) = a | The GCD and LCM of two equal positive integers are both equal to that integer. |
Prime Exponent Relationship | min(m,n) + max(m,n) = m + n | For each prime appearing in the two factorizations, the GCD and LCM exponents together reproduce the combined exponent in the product of the original integers. |
Examples
| Problem | Solution | Explanation |
|---|---|---|
Find the LCM of 12 and 18 using their GCD. | GCD(12,18) = 6. LCM = (12 × 18)/6 = 36. | Multiply the two integers and divide the result by their greatest common divisor. |
Find the GCD of 15 and 20 when their LCM is 60. | GCD = (15 × 20)/60 = 5. | The product relationship allows the GCD to be calculated directly. |
Verify the relationship for 24 and 36. | GCD(24,36) = 12 and LCM(24,36) = 72. Therefore, 12 × 72 = 864 and 24 × 36 = 864. | Both products are equal, confirming the GCD-LCM relationship. |
Find the LCM of two coprime integers 7 and 11. | GCD(7,11) = 1. Therefore, LCM = 7 × 11 = 77. | Since the integers have no common factor other than 1, their LCM equals their product. |
Find the LCM of 40 and 60 using prime factorization. | 40 = 2^3 × 5 and 60 = 2^2 × 3 × 5. LCM = 2^3 × 3 × 5 = 120. | The LCM uses the greatest exponent of every distinct prime factor appearing in either factorization. |
Applications
Calculating LCM when the GCD is already known.
Calculating GCD when the LCM is known.
Checking the consistency of GCD and LCM calculations.
Simplifying mathematical problems involving common factors and multiples.
Understanding prime factorization.
Solving number theory problems involving positive integers.
Prerequisites
Understanding of common factors and common multiples.
Knowledge of GCD and HCF.
Knowledge of LCM.
Understanding of prime factorization.
Basic multiplication and division.
Learning Objectives
State the relationship between GCD and LCM.
Calculate LCM using the GCD and original integers.
Calculate GCD using the LCM and original integers.
Verify the relationship using numerical examples.
Explain the relationship using prime factorization.
Recognize the special case of coprime integers.
Apply the relationship to solve numerical problems.
Common Mistakes
Adding GCD and LCM instead of multiplying them.
Dividing the product by the wrong value.
Confusing the GCD formula with the LCM formula.
Applying the formula without identifying the correct GCD or LCM.
Forgetting that the standard relationship is stated for positive integers.
Assuming that the GCD and LCM must always be different.
Practice Questions
Find the LCM of 18 and 30 using their GCD.
Find the GCD of 24 and 40 when their LCM is 120.
Verify the relationship for 16 and 24.
Find the LCM of two coprime numbers 13 and 17.
The GCD of two positive integers is 8 and their product is 960. Find their LCM.
Explain why the product of GCD and LCM equals the product of the original integers.
Key Takeaway
For any two positive integers, the product of their GCD and LCM equals the product of the integers themselves. This relationship makes it possible to calculate either value when the other is known.
Related Topics
SCI-MAT-002-044
SCI-MAT-002-045
SCI-MAT-002-046
SCI-MAT-002-047
SCI-MAT-002-048
SCI-MAT-002-049
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.
Suggest a correction or source · More in Arithmetic & Number Theory