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).

Let

n=2^{31}3^{19}.

How many positive integer divisors of

n^2

are less than

n

but do not divide

n?

Answer

Pair each divisor

d

n^2

with

\frac{n^2}{d}

Among the divisors below

n

, subtract those that already divide

n

The number

n^2=2^{62}3^{38}

has

63\cdot39=2457

divisors. Pairing

d

with

\frac{n^2}{d}

leaves only

n

unpaired, so

\frac{2457-1}{2}=1228

divisors lie below

n.

The number

n

has

32\cdot20=640

divisors, of which

639

are below

n.

Therefore the requested count is

1228-639=589.

Problem 6 in other years