1995 AIME Problems/Problem 6

Revision as of 15:14, 15 March 2008 by Azjps (talk | contribs) (fix answer)

Problem

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

Solution

We know that $n^2$ must have $63\times 39$ factors by its prime factorization. There are $\frac{63\times 39-1}{2} = 1228$ factors of $n^2$ that are less than $n$, because if they form pairs $a$, then there is one factor per pair that is less than $n$. There are $32\times20-1 = 639$ factors of $n$ that are less than $n$ itself. These are also factors of $n^2$. Therefore, there are $1228-639=\boxed{589}$ factors of $n$ that do not divide $n$.

See also

1995 AIME (ProblemsAnswer KeyResources)
Preceded by
Problem 5
Followed by
Problem 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions