Examkin

Question

Difficulty: Very hardProperties of Integers and Divisibility

Let nn be a positive integer such that nn has exactly 15 positive divisors. If nn is divisible by 18, but nn is NOT divisible by 8, what is the remainder when nn is divided by 7?

  1. A
    1
  2. 2Answer
  3. C
    3
  4. D
    4
  5. E
    5

Answer

The remainder when nn is divided by 7 is 2.
The total number of divisors of a positive integer with prime factorization p1ap2b…p_1^{a} p_2^{b} \dots is (a+1)(b+1)…(a+1)(b+1)\dots. Given that nn has 15 divisors, the possible exponent forms are 14 (since 14+1=1514+1=15) or 4 and 2 (since (4+1)(2+1)=15(4+1)(2+1)=15). Since nn is divisible by 18=2⋅3218 = 2 \cdot 3^2, its prime factors must be 2 and 3. The form p14p^{14} is eliminated because it contains only one prime factor. Testing the two permutations for p4⋅q2p^4 \cdot q^2:
1. If n=24⋅32=144n = 2^4 \cdot 3^2 = 144, nn is divisible by 8 (144/8=18144 / 8 = 18), which contradicts the condition that nn is NOT divisible by 8.
2. If n=22⋅34=324n = 2^2 \cdot 3^4 = 324, nn is divisible by 18 (324/18=18324 / 18 = 18) and is NOT divisible by 8 (324/8=40.5324 / 8 = 40.5).
Dividing 324 by 7 gives 324=7×46+2324 = 7 \times 46 + 2, so the remainder is 2.

Step-by-Step Solution

1
Analyze the divisor count formula for nn
The prime factorization of nn must be either p14p^{14} or p4⋅q2p^4 \cdot q^2 for distinct prime numbers pp and qq.
The total number of positive divisors of an integer with prime factorization p1ap2b…p_1^{a} p_2^{b} \dots is given by (a+1)(b+1)⋯=15(a+1)(b+1)\dots = 15. Since 15 factors as 15×115 \times 1 or 5×35 \times 3, the exponent structures are 14 or 4 and 2.
2
Apply the divisibility conditions by 18 and 8
nn must equal 22⋅34=3242^2 \cdot 3^4 = 324.
Because nn is divisible by 18=21⋅3218 = 2^1 \cdot 3^2, its prime factors must include both 2 and 3, ruling out p14p^{14}. Thus {p,q}={2,3}\{p, q\} = \{2, 3\}. If n=24⋅32=144n = 2^4 \cdot 3^2 = 144, then nn is divisible by 8 (232^3), violating the given constraint. Therefore, nn must be 22⋅34=3242^2 \cdot 3^4 = 324, which is divisible by 18 (324/18=18324 / 18 = 18) and not divisible by 8 (324/8=40.5324 / 8 = 40.5).
3
Compute the remainder when 324 is divided by 7
324 divided by 7 yields a quotient of 46 and a remainder of 2.
324=7×46+2324 = 7 \times 46 + 2 because 7×46=3227 \times 46 = 322.

Key Concept

Prime factorization, divisor count formula, and divisibility constraints
Rate this question

Topics

Properties of Integers and Divisibility

More questions from this topic