Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution 2)
m (→‎Solution 1)
Line 3: Line 3:
  
 
== Solution 1 ==
 
== 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</math>.
  
 
== Solution 2 ==
 
== Solution 2 ==

Revision as of 23:33, 14 December 2016

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^2$. Therefore, there are $1228-639=\boxed{589}$ factors of $n$ 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}$.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1995_AIME_Problems/Problem_6&oldid=81896"