Examkin

Question

Difficulty: HardPrime Numbers and Prime Factorization

A positive integer nn has exactly four distinct prime factors, the three smallest of which are 22, 33, and 55. If nn is divisible by 360360 and has exactly 4848 positive divisors, what is the minimum possible value of nn?

Answer: 2520

Answer

The minimum possible value of nn is 2520.
To minimize nn, we analyze its prime factorization n=2a×3b×5c×pdn = 2^a \times 3^b \times 5^c \times p^d, where pp is the fourth distinct prime factor. Divisibility by 360=23×32×51360 = 2^3 \times 3^2 \times 5^1 requires a≥3a \ge 3, b≥2b \ge 2, and c≥1c \ge 1. The number of positive divisors is given by (a+1)(b+1)(c+1)(d+1)=48(a+1)(b+1)(c+1)(d+1) = 48. To minimize nn, we pick the smallest prime greater than 5, which is p=7p = 7, and set d=1d = 1. This simplifies the divisor equation to (a+1)(b+1)(c+1)=24(a+1)(b+1)(c+1) = 24. Since a+1≥4a+1 \ge 4, b+1≥3b+1 \ge 3, and c+1≥2c+1 \ge 2, the minimal product of these terms is 4×3×2=244 \times 3 \times 2 = 24. This uniquely determines a=3a = 3, b=2b = 2, and c=1c = 1. Substituting these values gives n=23×32×51×71=2520n = 2^3 \times 3^2 \times 5^1 \times 7^1 = 2520.

Step-by-Step Solution

1
Determine the prime factorization of the divisor requirement.
360=23×32×51360 = 2^3 \times 3^2 \times 5^1.
Divisibility by 360 imposes lower bounds on the exponents of the prime factors 2, 3, and 5 in nn.
2
Formulate the general prime factorization for nn and state exponent constraints.
n=2a×3b×5c×pdn = 2^a \times 3^b \times 5^c \times p^d with a≥3a \ge 3, b≥2b \ge 2, c≥1c \ge 1, d≥1d \ge 1, and prime p>5p > 5.
nn has four distinct prime factors, three of which are 2, 3, and 5.
3
Apply the divisor counting formula to set up an algebraic equation.
(a+1)(b+1)(c+1)(d+1)=48(a+1)(b+1)(c+1)(d+1) = 48.
The number of positive divisors of n=p1e1p2e2…pkekn = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k} is given by (e1+1)(e2+1)…(ek+1)(e_1+1)(e_2+1)\dots(e_k+1).
4
Minimize nn by choosing optimal values for pp and dd.
p=7p = 7 and d=1d = 1, leading to (a+1)(b+1)(c+1)=24(a+1)(b+1)(c+1) = 24.
To make nn as small as possible, the fourth prime pp should be the smallest available prime (77) and its exponent dd should be minimized (11).
5
Solve for exponents aa, bb, and cc under the given inequality constraints.
a=3a = 3, b=2b = 2, c=1c = 1.
Since a+1≥4a+1 \ge 4, b+1≥3b+1 \ge 3, and c+1≥2c+1 \ge 2, the minimum possible product (a+1)(b+1)(c+1)(a+1)(b+1)(c+1) is 4×3×2=244 \times 3 \times 2 = 24. Hence, a=3,b=2,c=1a=3, b=2, c=1 is the unique solution.
6
Calculate the value of nn.
n=23×32×51×71=2520n = 2^3 \times 3^2 \times 5^1 \times 7^1 = 2520.
Multiplying out the prime factors yields the smallest integer matching all conditions.

Key Concept

Prime Factorization and Divisor Counting Constraints
Estimated Time:2m 0s
Rate this question

Topics

Prime Numbers and Prime Factorization

More questions from this topic