Examkin

Question

Difficulty: MediumPrime Factorization, GCD, and LCM

The greatest common divisor of a positive integer nn and 120120 is 2424, and their least common multiple is 25202520. How many positive divisors does nn have?

  1. A
    6
  2. B
    9
  3. C
    12
  4. 24Answer
  5. E
    48

Answer

24
First, write the prime factorizations of 120120, the gcd\text{gcd}, and the lcm\text{lcm}:
- 120=23⋅31⋅51120 = 2^3 \cdot 3^1 \cdot 5^1
- gcd(n,120)=24=23⋅31\text{gcd}(n, 120) = 24 = 2^3 \cdot 3^1
- lcm(n,120)=2520=23⋅32⋅51⋅71\text{lcm}(n, 120) = 2520 = 2^3 \cdot 3^2 \cdot 5^1 \cdot 7^1

For any prime pp, min⁡(vp(n),vp(120))=vp(gcd)\min(v_p(n), v_p(120)) = v_p(\text{gcd}) and max⁡(vp(n),vp(120))=vp(lcm)\max(v_p(n), v_p(120)) = v_p(\text{lcm}):
- For p=2p=2: min⁡(v2(n),3)=3\min(v_2(n), 3) = 3 and max⁡(v2(n),3)=3  ⟹  v2(n)=3\max(v_2(n), 3) = 3 \implies v_2(n) = 3.
- For p=3p=3: min⁡(v3(n),1)=1\min(v_3(n), 1) = 1 and max⁡(v3(n),1)=2  ⟹  v3(n)=2\max(v_3(n), 1) = 2 \implies v_3(n) = 2.
- For p=5p=5: min⁡(v5(n),1)=0  ⟹  v5(n)=0\min(v_5(n), 1) = 0 \implies v_5(n) = 0.
- For p=7p=7: max⁡(v7(n),0)=1  ⟹  v7(n)=1\max(v_7(n), 0) = 1 \implies v_7(n) = 1.

Thus, n=23⋅32⋅71n = 2^3 \cdot 3^2 \cdot 7^1. The number of positive divisors of nn is (3+1)(2+1)(1+1)=4⋅3⋅2=24(3+1)(2+1)(1+1) = 4 \cdot 3 \cdot 2 = 24. Therefore, the option specifying 24 is correct.

Step-by-Step Solution

1
Find the prime factorizations of 120120, gcd(n,120)\text{gcd}(n, 120), and lcm(n,120)\text{lcm}(n, 120).
120=23⋅31⋅51120 = 2^3 \cdot 3^1 \cdot 5^1, gcd=24=23⋅31\text{gcd} = 24 = 2^3 \cdot 3^1, and lcm=2520=23⋅32⋅51⋅71\text{lcm} = 2520 = 2^3 \cdot 3^2 \cdot 5^1 \cdot 7^1.
Expressing given quantities in terms of prime factors allows exact determination of the exponents in nn.
2
Determine the prime factorization of n=2a⋅3b⋅5c⋅7dn = 2^a \cdot 3^b \cdot 5^c \cdot 7^d.
a=3a = 3, b=2b = 2, c=0c = 0, and d=1d = 1, giving n=23⋅32⋅71=504n = 2^3 \cdot 3^2 \cdot 7^1 = 504.
Since min⁡(a,3)=3\min(a, 3) = 3 and max⁡(a,3)=3\max(a, 3) = 3, a=3a=3. Since min⁡(b,1)=1\min(b, 1) = 1 and max⁡(b,1)=2\max(b, 1) = 2, b=2b=2. Since min⁡(c,1)=0\min(c, 1) = 0, c=0c=0. Since max⁡(d,0)=1\max(d, 0) = 1, d=1d=1.
3
Calculate the number of positive divisors of nn.
(3+1)(2+1)(1+1)=4⋅3⋅2=24(3 + 1)(2 + 1)(1 + 1) = 4 \cdot 3 \cdot 2 = 24.
The total number of positive divisors for an integer p1e1p2e2⋯pkekp_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} is (e1+1)(e2+1)⋯(ek+1)(e_1 + 1)(e_2 + 1) \cdots (e_k + 1).

Key Concept

Prime Factorization, Greatest Common Divisor (GCD), Least Common Multiple (LCM), and Divisor Counting
Estimated Time:1m 30s
Rate this question

Topics

Prime Factorization, GCD, and LCM

More questions from this topic