Examkin

Question

Difficulty: HardPrime Factorization, GCD, and LCM

Two positive integers mm and nn satisfy gcd⁡(m,n)=20\gcd(m, n) = 20 and lcm(m,n)=4200\text{lcm}(m, n) = 4{}200. It is given that mm is divisible by 77 and has exactly 2424 positive integer divisors. If nn is a multiple of 33, what is the value of nn?

  1. 6060Answer
  2. B
    200200
  3. C
    300300
  4. D
    420420
  5. E
    600600

Answer

The value of nn is 6060.
Prime factorization reveals that gcd⁡(m,n)=22⋅30⋅51⋅70\gcd(m,n) = 2^2 \cdot 3^0 \cdot 5^1 \cdot 7^0 and lcm(m,n)=23⋅31⋅52⋅71\text{lcm}(m,n) = 2^3 \cdot 3^1 \cdot 5^2 \cdot 7^1. The condition that nn is a multiple of 33 fixes the exponent of 33 in nn to 11 (so mm has exponent 00). The condition that mm is a multiple of 77 fixes the exponent of 77 in mm to 11 (so nn has exponent 00). For m=2a⋅30⋅5c⋅71m = 2^a \cdot 3^0 \cdot 5^c \cdot 7^1, its divisor count equation 2(a+1)(c+1)=242(a+1)(c+1) = 24 simplifies to (a+1)(c+1)=12(a+1)(c+1) = 12. Since a∈{2,3}a \in \{2, 3\} and c∈{1,2}c \in \{1, 2\}, the only valid solution is a=3a=3 and c=2c=2. This leaves nn with exponents 22 for prime 22, 11 for prime 33, 11 for prime 55, and 00 for prime 77, giving n=22⋅31⋅51⋅70=60n = 2^2 \cdot 3^1 \cdot 5^1 \cdot 7^0 = 60.

Step-by-Step Solution

1
Express the GCD and LCM in prime factorized form.
gcd⁡(m,n)=20=22⋅30⋅51⋅70\gcd(m, n) = 20 = 2^2 \cdot 3^0 \cdot 5^1 \cdot 7^0 and lcm(m,n)=4200=23⋅31⋅52⋅71\text{lcm}(m, n) = 4{}200 = 2^3 \cdot 3^1 \cdot 5^2 \cdot 7^1.
The prime factor exponents of mm and nn must have minimums equal to the GCD exponents and maximums equal to the LCM exponents.
2
Determine the exponents of prime factors 33 and 77 for mm and nn.
Since nn is divisible by 33, exponent of 33 in nn is 11, so exponent of 33 in mm is 00. Since mm is divisible by 77, exponent of 77 in mm is 11, so exponent of 77 in nn is 00.
Each prime exponent in lcm(m,n)\text{lcm}(m, n) must belong to at least one of the numbers.
3
Use the divisor count of mm to find its remaining exponents for primes 22 and 55.
Let m=2a⋅30⋅5c⋅71m = 2^a \cdot 3^0 \cdot 5^c \cdot 7^1, where a∈{2,3}a \in \{2, 3\} and c∈{1,2}c \in \{1, 2\}. The number of positive divisors is (a+1)(0+1)(c+1)(1+1)=2(a+1)(c+1)=24(a+1)(0+1)(c+1)(1+1) = 2(a+1)(c+1) = 24, giving (a+1)(c+1)=12(a+1)(c+1) = 12. Testing a=2  ⟹  c=3a=2 \implies c=3 (invalid range). Testing a=3  ⟹  c=2a=3 \implies c=2 (valid). Thus m=23⋅30⋅52⋅71=1400m = 2^3 \cdot 3^0 \cdot 5^2 \cdot 7^1 = 1{}400.
The total number of positive integer divisors of p1e1p2e2⋯p_1^{e_1} p_2^{e_2} \cdots is given by (e1+1)(e2+1)⋯(e_1+1)(e_2+1)\cdots.
4
Determine the prime exponents for nn and calculate its value.
Since a=3a=3, nn gets 222^2. Since c=2c=2, nn gets 515^1. Together with 313^1 and 707^0, n=22⋅31⋅51⋅70=60n = 2^2 \cdot 3^1 \cdot 5^1 \cdot 7^0 = 60.
For each prime pp, the exponent in nn must match the bound opposite to mm to satisfy both gcd⁡\gcd and lcm\text{lcm}.

Key Concept

Prime exponent analysis of GCD and LCM alongside the divisor count formula
Rate this question

Topics

Prime Factorization, GCD, and LCM

More questions from this topic