Difference between revisions of "1995 AIME Problems/Problem 6"
(→Solution) |
|||
Line 2: | Line 2: | ||
Let <math>n=2^{31}3^{19}.</math> How many positive [[integer]] [[divisor]]s of <math>n^2</math> are less than <math>n_{}</math> but do not divide <math>n_{}</math>? | Let <math>n=2^{31}3^{19}.</math> How many positive [[integer]] [[divisor]]s of <math>n^2</math> are less than <math>n_{}</math> but do not divide <math>n_{}</math>? | ||
− | == Solution == | + | == Solution 1 == |
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^2</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^2</math>. | ||
+ | |||
+ | == Solution 2 == | ||
+ | |||
+ | Let <math>n=p_1^{k_1}p_2^{k_2}</math> for some prime <math>p_1,p_2</math>. Then <math>n^2</math> has <math>\frac{(2k_1+1)(2k_2+1)-1}{2}</math> factors less than <math>n</math>. | ||
+ | |||
+ | This simplifies to <math>\frac{4k_1k_2+2k_1+2k_2}{2}=2k_1k_2+k_1+k_2</math>. | ||
+ | |||
+ | The number of factors of <math>n</math> less than <math>n</math> is equal to <math>(k_1+1)(k_2+1)-1=k_1k_2+k_1+k_2</math>. | ||
+ | |||
+ | Thus, our general formula for <math>n=p_1^{k_1}p_2^{k_2}</math> is | ||
+ | |||
+ | <cmath> \text{Number\;of\;factors\;that\;satisfy\;conditions\;}=(2k_1k_2+k_1+k_2)-(k_1k_2+k_1+k_2)=k_1k_2<math>. </cmath> | ||
+ | |||
+ | Incorporating this into our problem gives </math>19\times31=\boxed{589}$. | ||
== See also == | == See also == |
Revision as of 15:26, 16 September 2014
Contents
[hide]Problem
Let How many positive integer divisors of are less than but do not divide ?
Solution 1
We know that must have factors by its prime factorization. If we group all of these factors (excluding ) into pairs that multiply to , then one factor per pair is less than , and so there are factors of that are less than . There are factors of , which clearly are less than , but are still factors of . Therefore, there are factors of that do not divide .
Solution 2
Let for some prime . Then has factors less than .
This simplifies to .
The number of factors of less than is equal to .
Thus, our general formula for is
Incorporating this into our problem gives </math>19\times31=\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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.