2
$\begingroup$

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?

  • 0
    Also, 'n' is a constant.2012-05-19

2 Answers 2

3

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}$

  • 0
    Great answer. Thanks :)2012-05-19
2

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)$

  • 0
    Equally great answer. Thanks :)2012-05-19