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

m (fix answer)
m (wording)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
We know that <math>n^2</math> must have <math>63\times 39</math> [[factor]]s by its [[prime factorization]]. There are <math>\frac{63\times 39-1}{2} = 1228</math> factors of <math>n^2</math> that are less than <math>n</math>, because if they form pairs <math>a</math>, then there is one factor per pair that is less than <math>n</math>. There are <math>32\times20-1 = 639</math> factors of <math>n</math> that are less than <math>n</math> itself. These are also factors of <math>n^2</math>. Therefore, there are <math>1228-639=\boxed{589}</math> factors of <math>n</math> that do not divide <math>n</math>.
+
We know that <math>n^2 = 2^{62}3^{38}</math> must have <math>(62+1)\times (38+1)</math> [[factor]]s by its [[prime factorization]]. If we group all of these factors (excluding <math>n</math>) into pairs that multiply to <math>n^2</math>, then one factor per pair is less than <math>n</math>, and so there are <math>\frac{63\times 39-1}{2} = 1228</math> factors of <math>n^2</math> that are less than <math>n</math>. There are <math>32\times20-1 = 639</math> factors of <math>n</math>, which clearly are less than <math>n</math>, but are still factors of <math>n^2</math>. Therefore, there are <math>1228-639=\boxed{589}</math> factors of <math>n</math> that do not divide <math>n</math>.
  
 
== See also ==
 
== See also ==

Revision as of 12:28, 18 June 2008

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

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