# Unique solutions for $ab = n ^ 2$

How many unique solutions are there to the equation $ab = n^2$ , where $n$ is a constant, $a,b \geq 1$ and $a,b,n$ are integers.

Is there any way of counting the number of solutions?

-
Are you sure you wanted to ask "how many unique solutions ..."? – DonAntonio May 19 '12 at 18:40
Yes, I mean (3,7) and (7,3) counts as 1.. – n0nChun May 19 '12 at 18:42
Also, 'n' is a constant. – n0nChun May 19 '12 at 18:43

For any $a$ that divides (i.e., goes into) $n^2$, there is a unique $b$ such that $ab=n^2$, namely $b=\frac{n^2}{a}$.

So, to figure out how many solutions $(a,b)$ there are, now we just have to determine how many possible $a$'s there are, i.e. how many divisors $n^2$ has.

If $n=p_1^{e_1}\cdots p_r^{e_r}$ is the prime factorization of $n$, then the prime factorization of $n^2$ is $$n^2=p_1^{2e_1}\cdots p_r^{2e_r}.$$ A number $a$ is a divisor of $n^2$ if and only if $$a=p_1^{d_1}\cdots p_r^{d_r}$$ where $0\leq d_i\leq 2e_i$ for each $i=1,2,\ldots, r$, so there are $$(1+2e_1)\cdots(1+2e_r)$$ divisors of $n^2$. However, because you indicated in the comments that you want $(a,b)$ and $(b,a)$ to count as the same solution, each divisor of $n^2$ other than $n$ will be counted twice ($a=n$ is the only divisor of $n^2$ for which $(a,b)=(b,a)$, because they are both equal to $(n,n)$). Thus, the number of distinct solutions is $$\frac{(1+2e_1)\cdots(1+2e_r)+1}{2}$$

-
Great answer. Thanks :) – n0nChun May 19 '12 at 19:29

In general, your question boils down to counting the number of divisors of $m$. In your question, $m = n^2$. If you know that prime factorization of $m$, i.e. say $m= p_1^{\alpha} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$, then by a simple counting argument the number of divisors of $m$ is given by $$d(m) = (1+\alpha_1)(1+\alpha_2) \cdots (1+\alpha_k)$$ In your case, if the prime decomposition of $n$ is $q_1^{\beta_1}q_2^{\beta_2} \cdots q_k^{\beta_k}$, then $$d(n^2) = (1+2 \beta_1)(1+2 \beta_2) \times \cdots \times (1+2 \beta_k)$$

If you do not care about the order i.e. if you count $ab = ba$ as just one solution, then the number of unique solutions to $ab = n^2$ is given by $$\frac{(1+2 \beta_1)(1+2 \beta_2) \times \cdots \times (1+2 \beta_k) + 1}{2}$$

You add $1$ and divide by $2$ to take into account that $n^2$ is a perfect square and not to distinguish between $ab$ and $ba$.

However, getting $d(m)$ as a function of $m$ is not trivial. You can however prove that $d(m)$ grows slowly than any power of $m$ and the average of the divisor function grows like $$\log(m) + (2 \gamma-1) + \mathcal{O} \left( \frac1{\sqrt{m}}\right)$$

-
Equally great answer. Thanks :) – n0nChun May 19 '12 at 19:29