1995 AIME Problems/Problem 6

From AoPSWiki

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 = 2^{62}3^{38}$ must have $(62+1)\times (38+1)$ factors by its prime factorization. If we group all of these factors (excluding $n$ ) into pairs that multiply to $n^2$ , then one factor per pair is less than $n$ , and so there are $\frac{63\times 39-1}{2} = 1228$ factors of $n^2$ that are less than $n$ . There are $32\times20-1 = 639$ factors of $n$ , which clearly are less than $n$ , but are still factors of $n^2$ . Therefore, there are $1228-639=\boxed{589}$ factors of $n$ that do not divide $n$ .

1995 AIME (Problems • Resources)
Preceded by Problem 5	Followed by Problem 7
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Personal tools

Navigation

Search

Toolbox

1995 AIME Problems/Problem 6

From AoPSWiki

Problem

Solution

See also