Examkin

Question

Difficulty: HardGreatest Common Divisor (GCD) and Least Common Multiple (LCM)

For two positive integers mm and nn, their prime factorizations are given by m=23×3a×5bm = 2^3 \times 3^a \times 5^b and n=2c×33×51n = 2^c \times 3^3 \times 5^1, where aa, bb, and cc are positive integer exponents. If the greatest common divisor of mm and nn is GCD(m,n)=360\text{GCD}(m, n) = 360 and their least common multiple is LCM(m,n)=108,000\text{LCM}(m, n) = 108,000, what is the value of a+b+ca + b + c?

  1. A
    77
  2. B
    88
  3. C
    99
  4. 1010Answer
  5. E
    1111

Answer

The correct value of a+b+ca + b + c is 1010.
First, find the prime factorizations of 360360 and 108,000108,000:
- 360=23×32×51360 = 2^3 \times 3^2 \times 5^1
- 108,000=25×33×53108,000 = 2^5 \times 3^3 \times 5^3

Using the properties of GCD and LCM:
- For base 22: GCD\text{GCD} power is 33 and LCM\text{LCM} power is 55. Since mm has 232^3, nn must have 2c2^c where c=5c = 5.
- For base 33: GCD\text{GCD} power is 22 and LCM\text{LCM} power is 33. Since nn has 333^3, mm must have 3a3^a where a=2a = 2.
- For base 55: GCD\text{GCD} power is 11 and LCM\text{LCM} power is 33. Since nn has 515^1, mm must have 5b5^b where b=3b = 3.

Summing these values gives a+b+c=2+3+5=10a + b + c = 2 + 3 + 5 = 10.

Step-by-Step Solution

1
Express GCD and LCM in prime factorized form.
GCD(m,n)=360=23×32×51\text{GCD}(m, n) = 360 = 2^3 \times 3^2 \times 5^1 and LCM(m,n)=108,000=25×33×53\text{LCM}(m, n) = 108,000 = 2^5 \times 3^3 \times 5^3.
Converting given numbers into prime powers allows direct comparison with the exponents of mm and nn.
2
Apply prime exponent min/max rules to determine aa, bb, and cc.
For prime 22: max⁡(3,c)=5  ⟹  c=5\max(3, c) = 5 \implies c = 5. For prime 33: min⁡(a,3)=2  ⟹  a=2\min(a, 3) = 2 \implies a = 2. For prime 55: max⁡(b,1)=3  ⟹  b=3\max(b, 1) = 3 \implies b = 3.
GCD\text{GCD} uses the minimum exponent for each prime factor, while LCM\text{LCM} uses the maximum exponent.
3
Sum the derived exponents aa, bb, and cc.
a+b+c=2+3+5=10a + b + c = 2 + 3 + 5 = 10.
The question asks for the sum a+b+ca + b + c.

Key Concept

Prime Factor Exponent Rule for GCD and LCM

Alternative Method

Use the product formula GCD(m,n)×LCM(m,n)=m×n\text{GCD}(m, n) \times \text{LCM}(m, n) = m \times n. Multiplying gives 360×108,000=38,880,000=28×35×54360 \times 108,000 = 38,880,000 = 2^8 \times 3^5 \times 5^4. Multiplying m×n=(23×3a×5b)×(2c×33×51)=23+c×3a+3×5b+1m \times n = (2^3 \times 3^a \times 5^b) \times (2^c \times 3^3 \times 5^1) = 2^{3+c} \times 3^{a+3} \times 5^{b+1}. Equating powers: 3+c=8  ⟹  c=53+c=8 \implies c=5, a+3=5  ⟹  a=2a+3=5 \implies a=2, b+1=4  ⟹  b=3b+1=4 \implies b=3. Thus a+b+c=2+3+5=10a+b+c = 2+3+5 = 10.
Estimated Time:2m 0s
Rate this question

Topics

Greatest Common Divisor (GCD) and Least Common Multiple (LCM)

More questions from this topic