Difference between revisions of "1995 AIME Problems/Problem 6"

Revision as of 00:45, 20 August 2018

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 1

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$ . Therefore, using complementary counting, there are $1228-639=\boxed{589}$ factors of $n^2$ that do not divide $n$ .

Solution 2

Let $n=p_1^{k_1}p_2^{k_2}$ for some prime $p_1,p_2$ . Then $n^2$ has $\frac{(2k_1+1)(2k_2+1)-1}{2}$ factors less than $n$ .

This simplifies to $\frac{4k_1k_2+2k_1+2k_2}{2}=2k_1k_2+k_1+k_2$ .

The number of factors of $n$ less than $n$ is equal to $(k_1+1)(k_2+1)-1=k_1k_2+k_1+k_2$ .

Thus, our general formula for $n=p_1^{k_1}p_2^{k_2}$ is

Number of factors that satisfy the above $=(2k_1k_2+k_1+k_2)-(k_1k_2+k_1+k_2)=k_1k_2$

Incorporating this into our problem gives $19\times31=\boxed{589}$ .

Solution 3

Consider divisors of $n^2: a,b$ such that $ab=n^2$ . WLOG, let $b\ge{a}. b=\frac{n}{a}

Then, it is easy to see that$ (Error compiling LaTeX. Unknown error_msg)a $will always be less than$ b $as we go down the divisor list of$ n^2 $until we hit$ n$.

Therefore, the median divisor of$ (Error compiling LaTeX. Unknown error_msg)n^2 $is$ n$.

Then, there are$ (Error compiling LaTeX. Unknown error_msg)(63)(39)=2457 $divisors of$ n^2 $. Exactly$ \frac{2457-1}{2}=1228 $of these divisors are$ <n $There are$ (32)(20)-1=639 $divisors of$ n $that are$ <n$.

Therefore, the answer is$ (Error compiling LaTeX. Unknown error_msg)1228-639=\boxed{589}$.

@@ Line 18: / Line 18: @@
 Incorporating this into our problem gives <math>19\times31=\boxed{589}</math>.
+== Solution 3 ==
+Consider divisors of <math>n^2: a,b</math> such that
+<math>ab=n^2</math>.
+WLOG, let <math>b\ge{a}. b=\frac{n}{a}
+Then, it is easy to see that </math>a<math> will always be less than </math>b<math> as we go down the divisor list of </math>n^2<math> until we hit </math>n<math>.
+Therefore, the median divisor of </math>n^2<math> is </math>n<math>.
+Then, there are </math>(63)(39)=2457<math> divisors of </math>n^2<math>. Exactly </math>\frac{2457-1}{2}=1228<math> of these divisors are </math><n<math>
+There are </math>(32)(20)-1=639<math> divisors of </math>n<math> that are </math><n<math>.
+Therefore, the answer is </math>1228-639=\boxed{589}$.
 == See also ==

1995 AIME (Problems • Answer Key • Resources)
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

Page

Toolbox

Search