Examkin

Question

Difficulty: HardFactors, Multiples, and Prime Factorization

A positive integer nn has the prime factorization 2a×3b×5c2^a \times 3^b \times 5^c, where aa, bb, and cc are positive integers. The greatest common divisor of nn and 840840 is 120120, and the least common multiple of nn and 9090 is 1,8001,800. If nn is not divisible by 99, what is the value of a+b+ca + b + c?

  1. A
    5
  2. 6Answer
  3. C
    7
  4. D
    8
  5. E
    9

Answer

6
The correct answer is 6. By analyzing the prime factorizations, the greatest common divisor condition GCD(n,840)=120\text{GCD}(n, 840) = 120 tells us that the exponents of the prime factors of nn satisfy a≥3a \geq 3, b≥1b \geq 1, and c≥1c \geq 1. The least common multiple condition LCM(n,90)=1,800\text{LCM}(n, 90) = 1,800 tells us that a=3a = 3, b≤2b \leq 2, and c=2c = 2. Finally, the condition that nn is not divisible by 9 requires b<2b < 2, which forces b=1b = 1. Summing these values gives 3+1+2=63 + 1 + 2 = 6.

Step-by-Step Solution

1
Find the prime factorizations of the given numbers.
840=23×31×51×71840 = 2^3 \times 3^1 \times 5^1 \times 7^1, 120=23×31×51120 = 2^3 \times 3^1 \times 5^1, 90=21×32×5190 = 2^1 \times 3^2 \times 5^1, and 1,800=23×32×521,800 = 2^3 \times 3^2 \times 5^2.
Decomposing the numbers into their prime factors allows us to apply the rules of Greatest Common Divisor (GCD) and Least Common Multiple (LCM) on the exponents.
2
Analyze the GCD condition.
Since GCD(n,840)=120\text{GCD}(n, 840) = 120, we have min⁡(a,3)=3\min(a, 3) = 3, min⁡(b,1)=1\min(b, 1) = 1, and min⁡(c,1)=1\min(c, 1) = 1. This implies a≥3a \geq 3, b≥1b \geq 1, and c≥1c \geq 1.
The GCD of two numbers takes the minimum exponent for each prime factor present in both numbers.
3
Analyze the LCM condition.
Since LCM(n,90)=1,800\text{LCM}(n, 90) = 1,800, we have max⁡(a,1)=3\max(a, 1) = 3, max⁡(b,2)=2\max(b, 2) = 2, and max⁡(c,1)=2\max(c, 1) = 2. This implies a=3a = 3, b≤2b \leq 2, and c=2c = 2.
The LCM of two numbers takes the maximum exponent for each prime factor present in either number.
4
Apply the divisibility constraint to determine the exponents.
From previous steps, a=3a = 3 and c=2c = 2. The exponent bb must satisfy 1≤b≤21 \leq b \leq 2. Since nn is not divisible by 9=329 = 3^2, the exponent of 3 in the factorization of nn must be strictly less than 2. Thus, b=1b = 1.
If b=2b = 2, then nn would contain 323^2, making it divisible by 9, which violates the given constraint.
5
Calculate the sum a+b+ca + b + c.
a+b+c=3+1+2=6a + b + c = 3 + 1 + 2 = 6.
Adding the determined exponents yields the final requested value.

Key Concept

Using prime factorizations to find the greatest common divisor and least common multiple of integers.

Alternative Method

Instead of checking each prime factor independently, we can find the value of nn directly. Since GCD(n,840)=120\text{GCD}(n, 840) = 120, nn must be a multiple of 120120. The multiples of 120120 are 120,240,360,480,600,720,840,…120, 240, 360, 480, 600, 720, 840, \dots. We test which of these multiples satisfies LCM(n,90)=1,800\text{LCM}(n, 90) = 1,800 and is not divisible by 99. Since 1,800=15×1201,800 = 15 \times 120, nn must divide 1,8001,800. The divisors of 1,8001,800 that are multiples of 120120 are 120,240,360,600,900,1,800120, 240, 360, 600, 900, 1,800. Among these, only 600600 has a greatest common divisor of 120120 with 840840, is not divisible by 99, and has LCM(600,90)=1,800\text{LCM}(600, 90) = 1,800. Thus, n=600=23×31×52n = 600 = 2^3 \times 3^1 \times 5^2, which gives a+b+c=3+1+2=6a+b+c = 3+1+2 = 6.
Estimated Time:2m 0s
Rate this question

Topics

Factors, Multiples, and Prime Factorization

More questions from this topic