# positive divisor

• Jan 14th 2011, 02:45 AM
rcs
positive divisor
Let n = 2^31 3^19. How many positive divisors of n^2 are less than n but
do not divide n?
• Jan 14th 2011, 02:57 AM
tonio
Quote:

Originally Posted by rcs
Let n = 2^31 3^19. How many positive divisors of n^2 are less than n but
do not divide n?

Lemma: if $\displaystyle n=p_1^{a_1}\cdot\ldots\cdot p_k^{a_k}$ is the prime decomposition of a natural number $\displaystyle n$, then the number of positive divisors of n is $\displaystyle \prod\limits_{i=1}^k(a_i+1)$

Well, now apply the above both to $\displaystyle n\,\,and\,\,n^2$ and do some maths...

Tonio
• Jan 14th 2011, 08:04 AM
Opalg
Quote:

Originally Posted by rcs
Let $\displaystyle n = 2^{31}\cdot 3^{19}$. How many positive divisors of $\displaystyle n^2$ are less than $\displaystyle n$ but
do not divide $\displaystyle n$?

A divisor of $\displaystyle n^2$ must be of the form $\displaystyle 2^p\cdot3^q$, with $\displaystyle 0\leqslant p\leqslant 62$ and $\displaystyle 0\leqslant q\leqslant 38$. If it does not divide $\displaystyle n$ then either $\displaystyle p>31$ or $\displaystyle q>19$.

Now comes the tricky part. The remaining condition is that $\displaystyle 2^p\cdot3^q < n$. I suggest that you investigate this by choosing a random value of p between 31 and 62, say p=45, and looking at how many values of q satisfy the condition $\displaystyle 2^{45}\cdot 3^q <2^{31}\cdot 3^{19}$. [Hint: take logs.] That may possibly give you some insight into how to tackle the problem in general.
• Jan 15th 2011, 12:50 AM
rcs
it is said that the answer is 589 but i dont know how it is reached to this.
• Jan 15th 2011, 02:35 AM
emakarov
This question has already been discussed, but I have not tried to find a more elegant solution.