Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
Great answer. Thanks :) –  n0nChun May 19 '12 at 19:29
add comment

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

share|improve this answer
    
Equally great answer. Thanks :) –  n0nChun May 19 '12 at 19:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.