The Central Idea
Given positive integers \(a\) and \(b\), two related questions arise:
- What is the largest positive integer that divides both \(a\) and \(b\)?
- What is the smallest positive integer that is divisible by both \(a\) and \(b\)?
The answers are the greatest common divisor and the least common multiple.
\[ \boxed{\gcd(a,b)} \qquad\text{and}\qquad \boxed{\operatorname{lcm}(a,b)}. \]Common Divisors
A common divisor of two integers is a positive integer that divides both.
Consider \(18\) and \(30\).
The positive divisors of \(18\) are
\[ 1,\ 2,\ 3,\ 6,\ 9,\ 18, \]while the positive divisors of \(30\) are
\[ 1,\ 2,\ 3,\ 5,\ 6,\ 10,\ 15,\ 30. \]Their common divisors are
\[ \boxed{1,\ 2,\ 3,\ 6}. \]The Greatest Common Divisor
The greatest common divisor, abbreviated GCD, is the greatest positive integer that divides each of the given integers.
From the common divisors of \(18\) and \(30\),
\[ 1,\ 2,\ 3,\ 6, \]the largest is \(6\). Therefore,
\[ \boxed{\gcd(18,30)=6}. \]Another Name: Greatest Common Factor
In elementary arithmetic and algebra, the greatest common divisor is also often called the greatest common factor, or GCF.
Thus
\[ \gcd(18,30)=6 \]and
\[ \operatorname{GCF}(18,30)=6 \]express the same numerical relationship.
Number theory usually favors the term greatest common divisor.
Common Multiples
A common multiple of two positive integers is a positive integer divisible by both.
The positive multiples of \(6\) begin
\[ 6,\ 12,\ 18,\ 24,\ 30,\ 36,\ 42,\ 48,\ldots \]and the positive multiples of \(8\) begin
\[ 8,\ 16,\ 24,\ 32,\ 40,\ 48,\ldots \]Shared values include
\[ 24,\ 48,\ 72,\ldots \]The Least Common Multiple
The least common multiple, abbreviated LCM, is the smallest positive integer that is a multiple of each given integer.
For \(6\) and \(8\), the first positive common multiple is \(24\). Therefore,
\[ \boxed{\operatorname{lcm}(6,8)=24}. \]Divisor Language and Multiple Language
GCD and LCM point in opposite structural directions.
- The GCD looks downward for a largest shared divisor.
- The LCM looks upward for a smallest shared multiple.
For \(12\) and \(18\),
\[ \gcd(12,18)=6 \]because \(6\) divides both, while
\[ \operatorname{lcm}(12,18)=36 \]because \(36\) is the first positive number divisible by both.
Finding a GCD by Listing Divisors
For small numbers, one direct method is to list positive divisors.
Find \(\gcd(24,36)\).
Divisors of \(24\):
\[ 1,\ 2,\ 3,\ 4,\ 6,\ 8,\ 12,\ 24. \]Divisors of \(36\):
\[ 1,\ 2,\ 3,\ 4,\ 6,\ 9,\ 12,\ 18,\ 36. \]The common divisors are
\[ 1,\ 2,\ 3,\ 4,\ 6,\ 12. \]Therefore,
\[ \boxed{\gcd(24,36)=12}. \]Finding an LCM by Listing Multiples
For small numbers, list multiples until the first shared positive value appears.
Find \(\operatorname{lcm}(9,12)\).
Multiples of \(9\):
\[ 9,\ 18,\ 27,\ 36,\ 45,\ldots \]Multiples of \(12\):
\[ 12,\ 24,\ 36,\ 48,\ldots \]The first shared positive value is \(36\), so
\[ \boxed{\operatorname{lcm}(9,12)=36}. \]Why Listing Has Limits
Listing divisors or multiples works well for small integers, but it becomes inefficient as the numbers grow.
For larger problems, prime factorization exposes the shared structure more directly.
This method relies on writing each positive integer greater than \(1\) as a product of primes.
GCD from Prime Factorization
Factor \(72\) and \(120\):
\[ 72=2^3\cdot3^2 \]and
\[ 120=2^3\cdot3\cdot5. \]To form the GCD, keep only prime factors shared by both numbers and use the smaller exponent of each shared prime.
\[ \gcd(72,120)=2^3\cdot3. \]Therefore,
\[ \boxed{\gcd(72,120)=24}. \]Why the GCD Uses Smaller Exponents
A common divisor must fit completely into both numbers.
In
\[ 72=2^3\cdot3^2 \]and
\[ 120=2^3\cdot3^1\cdot5, \]both numbers contain \(2^3\), but they share only one factor of \(3\).
Using \(3^2\) would create a number that does not divide \(120\). Therefore the smaller exponent is required.
LCM from Prime Factorization
Use the same factorizations:
\[ 72=2^3\cdot3^2 \]and
\[ 120=2^3\cdot3\cdot5. \]To form the LCM, include every prime appearing in either factorization and use the larger exponent of each prime.
\[ \operatorname{lcm}(72,120)=2^3\cdot3^2\cdot5. \]Therefore,
\[ \boxed{\operatorname{lcm}(72,120)=360}. \]Why the LCM Uses Larger Exponents
A common multiple must contain enough prime factors to be divisible by each original number.
The number \(72\) requires
\[ 2^3\cdot3^2, \]while \(120\) requires
\[ 2^3\cdot3\cdot5. \]The smallest number satisfying both requirements must contain
\[ 2^3,\qquad3^2,\qquad5. \]A Compact Prime-Exponent View
Suppose
\[ a=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n} \]and
\[ b=p_1^{\beta_1}p_2^{\beta_2}\cdots p_n^{\beta_n}, \]allowing an exponent of \(0\) when a prime does not occur.
Then the GCD uses
\[ \boxed{\min(\alpha_i,\beta_i)} \]for each prime, while the LCM uses
\[ \boxed{\max(\alpha_i,\beta_i)}. \]Example: Prime-Factorization Method
Find the GCD and LCM of \(84\) and \(126\).
\[ 84=2^2\cdot3\cdot7 \] \[ 126=2\cdot3^2\cdot7. \]For the GCD, take the smaller exponent of each shared prime:
\[ \gcd(84,126)=2\cdot3\cdot7=42. \]For the LCM, take the larger exponent of every prime:
\[ \operatorname{lcm}(84,126)=2^2\cdot3^2\cdot7=252. \]Thus,
\[ \boxed{\gcd(84,126)=42} \qquad\text{and}\qquad \boxed{\operatorname{lcm}(84,126)=252}. \]Relatively Prime Integers
Two positive integers are relatively prime, or coprime, when their greatest common divisor is \(1\).
\[ \boxed{\gcd(a,b)=1}. \]For example,
\[ \gcd(8,15)=1. \]Therefore \(8\) and \(15\) are relatively prime even though neither number is itself prime.
Relatively Prime Does Not Mean Prime
The phrase “relatively prime” describes a relationship between numbers. It does not require either number to be prime.
For example,
\[ 8=2^3 \qquad\text{and}\qquad 9=3^2 \]are both composite, but they have no positive common divisor greater than \(1\).
\[ \boxed{\gcd(8,9)=1}. \]LCM of Relatively Prime Numbers
If \(a\) and \(b\) are relatively prime, their prime factorizations share no prime factors.
Therefore their least common multiple is simply their product:
\[ \boxed{\gcd(a,b)=1\implies\operatorname{lcm}(a,b)=ab}. \]For example,
\[ \operatorname{lcm}(8,15)=8\cdot15=120. \]When One Number Divides the Other
Suppose \(a\mid b\) with \(a,b>0\).
Then every divisor of \(a\) that can be common to both is bounded above by \(a\), and \(a\) itself divides both. Therefore,
\[ \boxed{\gcd(a,b)=a}. \]Also, \(b\) is already a multiple of both numbers, so
\[ \boxed{\operatorname{lcm}(a,b)=b}. \]Example: One Number Divides the Other
Since
\[ 12\mid60, \]we can immediately conclude
\[ \boxed{\gcd(12,60)=12} \]and
\[ \boxed{\operatorname{lcm}(12,60)=60}. \]The Product Relationship
For positive integers \(a\) and \(b\), the GCD and LCM satisfy
\[ \boxed{\gcd(a,b)\operatorname{lcm}(a,b)=ab}. \]Equivalently,
\[ \boxed{ \operatorname{lcm}(a,b)= \frac{ab}{\gcd(a,b)} }. \]This provides a convenient way to find the LCM once the GCD is known.
Why the Product Relationship Works
In prime factorization, the GCD takes the smaller exponent of each prime and the LCM takes the larger exponent.
For any two exponents \(\alpha\) and \(\beta\),
\[ \min(\alpha,\beta)+\max(\alpha,\beta)=\alpha+\beta. \]Multiplying the GCD and LCM therefore restores exactly the combined prime exponents occurring in \(ab\).
Example: Finding the LCM from the GCD
Suppose
\[ \gcd(48,180)=12. \]Then
\[ \operatorname{lcm}(48,180) = \frac{48\cdot180}{12}. \]Simplify:
\[ \operatorname{lcm}(48,180)=4\cdot180=720. \]Therefore,
\[ \boxed{\operatorname{lcm}(48,180)=720}. \]GCD of More Than Two Integers
The greatest common divisor can be extended to several integers.
For example, find
\[ \gcd(24,36,60). \]The positive integers dividing all three include
\[ 1,\ 2,\ 3,\ 4,\ 6,\ 12. \]The greatest is \(12\), so
\[ \boxed{\gcd(24,36,60)=12}. \]LCM of More Than Two Integers
The least common multiple also extends naturally.
Find
\[ \operatorname{lcm}(4,6,10). \]Prime factorizations give
\[ 4=2^2,\qquad6=2\cdot3,\qquad10=2\cdot5. \]Take the largest exponent required for each prime:
\[ 2^2\cdot3\cdot5=60. \]Therefore,
\[ \boxed{\operatorname{lcm}(4,6,10)=60}. \]GCD and Fraction Reduction
The GCD identifies the largest factor that can be cancelled from the numerator and denominator of a fraction.
Consider
\[ \frac{84}{126}. \]Since
\[ \gcd(84,126)=42, \]divide both terms by \(42\):
\[ \frac{84}{126} = \frac{2}{3}. \]The reduced numerator and denominator are relatively prime.
LCM and Common Denominators
The LCM provides the least common denominator for fractions whose denominators are positive integers.
For
\[ \frac{1}{12} \qquad\text{and}\qquad \frac{1}{18}, \]we have
\[ \operatorname{lcm}(12,18)=36. \]Therefore \(36\) is the least common denominator.
LCM and Repeating Cycles
LCM naturally appears when independent repeating processes must coincide.
Suppose one event occurs every \(6\) days and another every \(8\) days. If they occur together today, the next shared occurrence is after
\[ \operatorname{lcm}(6,8)=24 \]days.
GCD and Equal Grouping
GCD appears when a collection must be divided into the largest possible equal units.
Suppose \(48\) red objects and \(60\) blue objects must be divided into identical groups with no objects left over.
The largest possible number of groups is
\[ \gcd(48,60)=12. \]Each group contains
\[ \frac{48}{12}=4 \]red objects and
\[ \frac{60}{12}=5 \]blue objects.
GCD and LCM Are Different Questions
The wording of a problem often reveals which concept is needed.
GCD language often involves:
- largest equal groups;
- greatest shared measure;
- largest common factor;
- reducing or simplifying.
LCM language often involves:
- first shared occurrence;
- smallest common cycle;
- least common denominator;
- smallest quantity divisible by several numbers.
Common Error: Multiplying to Find Every LCM
The product \(ab\) is always a common multiple of positive integers \(a\) and \(b\), but it is not always the least common multiple.
For example,
\[ 12\cdot18=216, \]but
\[ \boxed{\operatorname{lcm}(12,18)=36}. \]Shared prime factors allow a much smaller common multiple.
Common Error: Using Larger Exponents for the GCD
Consider
\[ 24=2^3\cdot3 \]and
\[ 36=2^2\cdot3^2. \]Using the larger exponents would produce
\[ 2^3\cdot3^2=72, \]which does not divide either number.
The GCD must use the smaller shared exponents:
\[ \boxed{\gcd(24,36)=2^2\cdot3=12}. \]Common Error: Using Smaller Exponents for the LCM
With the same numbers,
\[ 24=2^3\cdot3, \qquad 36=2^2\cdot3^2, \]using smaller exponents gives \(12\), which is not a multiple of \(24\) or \(36\).
The LCM uses the larger exponents:
\[ \boxed{\operatorname{lcm}(24,36)=2^3\cdot3^2=72}. \]Common Error: Omitting a Prime from the LCM
Suppose
\[ 20=2^2\cdot5 \]and
\[ 27=3^3. \]The LCM must include every prime required by either number:
\[ \boxed{\operatorname{lcm}(20,27)=2^2\cdot3^3\cdot5=540}. \]A prime factor does not need to appear in both numbers to appear in the LCM.
Common Error: Confusing Relatively Prime with Prime
The integers \(14\) and \(25\) are both composite:
\[ 14=2\cdot7, \qquad 25=5^2. \]But they share no prime factor, so
\[ \boxed{\gcd(14,25)=1}. \]Thus they are relatively prime.
A Reliable Procedure for Finding a GCD
- For small numbers, list positive divisors if convenient.
- For a factorization method, write each number as a product of primes.
- Identify the primes appearing in every number.
- For each shared prime, choose the smallest exponent.
- Multiply the selected prime powers.
- Check that the result divides every original number.
A Reliable Procedure for Finding an LCM
- For small numbers, list positive multiples if convenient.
- For a factorization method, write each number as a product of primes.
- Include every prime appearing in any factorization.
- For each prime, choose the largest exponent that appears.
- Multiply the selected prime powers.
- Check that every original number divides the result.
Example: Full GCD and LCM Workflow
Find the GCD and LCM of \(90\) and \(168\).
Factor:
\[ 90=2\cdot3^2\cdot5 \] \[ 168=2^3\cdot3\cdot7. \]The shared primes are \(2\) and \(3\). Use smaller exponents:
\[ \gcd(90,168)=2\cdot3=6. \]For the LCM, use all primes with their larger exponents:
\[ \operatorname{lcm}(90,168) = 2^3\cdot3^2\cdot5\cdot7. \]Therefore,
\[ \boxed{\gcd(90,168)=6} \]and
\[ \boxed{\operatorname{lcm}(90,168)=2520}. \]Checking with the Product Relationship
For the previous example,
\[ 6\cdot2520=15120 \]and
\[ 90\cdot168=15120. \]Thus
\[ \gcd(90,168)\operatorname{lcm}(90,168)=90\cdot168, \]as expected.
Practice 1: List Common Divisors
Find all positive common divisors of
\[ 20\text{ and }30, \]then identify their GCD.
Practice 2: List Common Multiples
Find
\[ \operatorname{lcm}(8,12) \]by listing multiples.
Practice 3: Prime-Factorization GCD
Find
\[ \gcd(48,72). \]Practice 4: Prime-Factorization LCM
Find
\[ \operatorname{lcm}(48,72). \]Practice 5: Relatively Prime
Determine whether
\[ 16\text{ and }45 \]are relatively prime.
Practice 6: One Number Divides the Other
Find
\[ \gcd(18,90) \]and
\[ \operatorname{lcm}(18,90). \]Practice 7: Use the Product Relationship
Suppose
\[ \gcd(42,60)=6. \]Find
\[ \operatorname{lcm}(42,60). \]Practice 8: Three Integers
Find
\[ \gcd(36,60,84). \]Practice 9: Repeating Cycles
One signal repeats every \(12\) seconds and another every \(18\) seconds. If they occur together now, after how many seconds will they next occur together?
Practice 10: Equal Grouping
A collection contains \(72\) items of one type and \(96\) of another. What is the greatest number of identical groups that can be formed with no items left over?
Practice Answers
Practice 1
The positive common divisors of \(20\) and \(30\) are
\[ 1,\ 2,\ 5,\ 10. \]Therefore,
\[ \boxed{\gcd(20,30)=10}. \]Practice 2
Multiples of \(8\) include
\[ 8,\ 16,\ 24,\ldots \]and multiples of \(12\) include
\[ 12,\ 24,\ldots \]so
\[ \boxed{\operatorname{lcm}(8,12)=24}. \]Practice 3
\[ 48=2^4\cdot3, \qquad 72=2^3\cdot3^2. \]Use the smaller exponents:
\[ \boxed{\gcd(48,72)=2^3\cdot3=24}. \]Practice 4
Use the larger exponents:
\[ \boxed{\operatorname{lcm}(48,72)=2^4\cdot3^2=144}. \]Practice 5
\[ 16=2^4, \qquad 45=3^2\cdot5. \]They share no prime factor, so
\[ \boxed{\gcd(16,45)=1}. \]Therefore they are relatively prime.
Practice 6
Since \(18\mid90\),
\[ \boxed{\gcd(18,90)=18} \]and
\[ \boxed{\operatorname{lcm}(18,90)=90}. \]Practice 7
\[ \operatorname{lcm}(42,60) = \frac{42\cdot60}{6}. \]Therefore,
\[ \boxed{\operatorname{lcm}(42,60)=420}. \]Practice 8
\[ 36=2^2\cdot3^2, \qquad 60=2^2\cdot3\cdot5, \qquad 84=2^2\cdot3\cdot7. \]The shared prime powers are
\[ 2^2\cdot3. \]Thus
\[ \boxed{\gcd(36,60,84)=12}. \]Practice 9
\[ \operatorname{lcm}(12,18)=36. \]The signals next occur together after
\[ \boxed{36\text{ seconds}}. \]Practice 10
\[ \gcd(72,96)=24. \]Therefore the greatest possible number of identical groups is
\[ \boxed{24}. \]What to Remember
- The GCD is the greatest positive integer dividing all given integers.
- The LCM is the least positive integer divisible by all given integers.
- For a GCD from prime factorizations, use shared primes with smaller exponents.
- For an LCM, use every required prime with the largest exponent.
- Two integers are relatively prime when their GCD is \(1\).
- If \(a\mid b\), then \(\gcd(a,b)=a\) and \(\operatorname{lcm}(a,b)=b\).
- For positive integers, \(\gcd(a,b)\operatorname{lcm}(a,b)=ab\).
- GCD is useful for shared grouping and reduction; LCM is useful for shared cycles and common denominators.
The central distinction is: GCD searches among shared divisors, while LCM searches among shared multiples.
Where We Go Next
Listing divisors and prime factorization can find greatest common divisors, but number theory has a faster method that works directly with division and remainders. The next lesson, The Euclidean Algorithm, develops that procedure and shows why repeated remainder calculations preserve the greatest common divisor.