1995 AIME Problem 6

Attempt Problem 6 of the 1995 AIME below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 1995 AIME solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

6.

Let n=231319.n=2^{31}3^{19}. How many positive integer divisors of n2n^2 are less than nn but do not divide n?n?

Answer: 589
Concepts:factor countingpairing and groupingprime factorization
Difficulty rating: 2270
Small Hint:

Pair each divisor dd of n2n^2 with n2d\frac{n^2}{d}

Big Hint:

Among the divisors below nn, subtract those that already divide nn

Solution:

The number n2=262338n^2=2^{62}3^{38} has 6339=245763\cdot39=2457 divisors. Pairing dd with n2d\frac{n^2}{d} leaves only nn unpaired, so 245712=1228\frac{2457-1}{2}=1228 divisors lie below n.n. The number nn has 3220=64032\cdot20=640 divisors, of which 639639 are below n.n. Therefore the requested count is 1228639=589.1228-639=589.

← Problem 5#5
Full Exam

Problem 6 in Other Years