# Thread: How many positive divisors of n^2...

1. ## How many positive divisors of n^2...

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

2. $\displaystyle \displaystyle n^2=(2^{31}*3^{19})^2=2^{62}*3^{38}$

$\displaystyle \displaystyle \tau (p^e)=e+1$

p is prime and $\displaystyle e\in\mathbb{Z}$ .

$\displaystyle \displaystyle \tau (n^2)=\tau (2^{62})*\tau (3^{38})=(62+1)(38+1)=63*39=2457$

Then, from here, we subtract 1 because the highest factor is $\displaystyle n^2$.

$\displaystyle 2457-1=2456$

Just read the factors can't divide n.

We know that $\displaystyle n|n, \ 1|n, \ 2|n, \ 3|n$.

Therefore, we must subtract $\displaystyle n, 1, 31, 19$

31 are the number of multiple of 2s, 19 are the multiple of 3s, and 19 are the multiples of 6.

However, this includes some overlap. Your job is to figure out how many to add back in.

3. Suppose $\displaystyle m\mid n^2$. Then there exist some $\displaystyle i$ and $\displaystyle j$ such that $\displaystyle m=2^i\cdot 3^j$. Moreover, $\displaystyle m\nmid n$ iff $\displaystyle i\ge 32$ or $\displaystyle j\ge 20$. Next, $\displaystyle \lfloor\log_2n\rfloor=61$ and $\displaystyle \lfloor\log_3n\rfloor=38$. Therefore, if $\displaystyle m\nmid n$ and $\displaystyle m < n$, then either (1) $\displaystyle 32\le i\le61$ or (2) $\displaystyle 20\le j\le 38$. Note that (1) and (2) are mutually exclusive. Conversely, for each $\displaystyle 32\le i\le61$ and each $\displaystyle 0\le j\le\lfloor\log_3(n/2^i)\rfloor$, $\displaystyle 2^i\cdot 3^j<n$ and $\displaystyle 2^i\cdot 3^j\nmid n$. Similarly, for each $\displaystyle 20\le j\le38$ and each $\displaystyle 0\le i\le\lfloor\log_2(n/3^j)\rfloor$, $\displaystyle 2^i\cdot 3^j<n$ and $\displaystyle 2^i\cdot 3^j\nmid n$.

Therefore, the answer is $\displaystyle \displaystyle\sum_{i=32}^{61}(\lfloor\log_3(n/2^i)\rfloor+1)+\sum_{j=20}^{38}(\lfloor\log_2(n/3^j)\rfloor+1)$. According to my brute-force calculations, this is 589.

Maybe someone will figure out a more elegant solution.

4. thanks a lot sir emakarov, i got that problem from a book but does not have a solution shown, but i has an answer of 589, you so amazing. thank you so much.