Examkin

Question

Difficulty: MediumPrime Factorization, GCD, and LCM

Let n=2a⋅3b⋅5cn = 2^a \cdot 3^b \cdot 5^c be a positive integer, where aa, bb, and cc are non-negative integers. If the greatest common divisor of nn and 360360 is 4545, and the least common multiple of nn and 9090 is 450450, what is the value of a+b+ca + b + c?

  1. A
    2
  2. B
    3
  3. 4Answer
  4. D
    5
  5. E
    6

Answer

The value of a+b+ca + b + c is 44.
Prime factorizing the given values yields 360=23⋅32⋅51360 = 2^3 \cdot 3^2 \cdot 5^1, 45=20⋅32⋅5145 = 2^0 \cdot 3^2 \cdot 5^1, 90=21⋅32⋅5190 = 2^1 \cdot 3^2 \cdot 5^1, and 450=21⋅32⋅52450 = 2^1 \cdot 3^2 \cdot 5^2. Because gcd⁡(n,360)=45\gcd(n, 360) = 45, taking the minimum exponent of 2 implies min⁡(a,3)=0\min(a, 3) = 0, so a=0a = 0. Taking the minimum exponent of 3 implies b≥2b \ge 2, and for 5 implies c≥1c \ge 1. Next, using lcm(n,90)=450\text{lcm}(n, 90) = 450, taking the maximum exponent of 3 gives max⁡(b,2)=2\max(b, 2) = 2, which forces b=2b = 2. Taking the maximum exponent of 5 gives max⁡(c,1)=2\max(c, 1) = 2, which forces c=2c = 2. Therefore, a+b+c=0+2+2=4a + b + c = 0 + 2 + 2 = 4.

Step-by-Step Solution

1
Express all given integers in their prime factorizations.
360=23⋅32⋅51360 = 2^3 \cdot 3^2 \cdot 5^1, 45=32⋅51=20⋅32⋅5145 = 3^2 \cdot 5^1 = 2^0 \cdot 3^2 \cdot 5^1, 90=21⋅32⋅5190 = 2^1 \cdot 3^2 \cdot 5^1, and 450=21⋅32⋅52450 = 2^1 \cdot 3^2 \cdot 5^2.
Prime factorizations allow determination of exponents using exponent rules for GCD and LCM.
2
Apply the GCD condition gcd⁡(n,360)=45\gcd(n, 360) = 45.
min⁡(a,3)=0  ⟹  a=0\min(a, 3) = 0 \implies a = 0, min⁡(b,2)=2  ⟹  b≥2\min(b, 2) = 2 \implies b \ge 2, and min⁡(c,1)=1  ⟹  c≥1\min(c, 1) = 1 \implies c \ge 1.
The greatest common divisor takes the minimum exponent for each prime factor shared between the numbers.
3
Apply the LCM condition lcm(n,90)=450\text{lcm}(n, 90) = 450 using a=0a = 0.
max⁡(b,2)=2  ⟹  b≤2\max(b, 2) = 2 \implies b \le 2 (so b=2b = 2), and max⁡(c,1)=2  ⟹  c=2\max(c, 1) = 2 \implies c = 2.
The least common multiple takes the maximum exponent for each prime factor.
4
Calculate the sum a+b+ca + b + c.
a+b+c=0+2+2=4a + b + c = 0 + 2 + 2 = 4.
Adding the individual prime factor exponents yields the requested sum.

Key Concept

Relating prime factor exponents to GCD (minimum powers) and LCM (maximum powers)
Estimated Time:1m 30s
Rate this question

Topics

Prime Factorization, GCD, and LCM

More questions from this topic