# Math Help - LCM

1. ## LCM

I am having troubles with this problem:

For any n find all pairs $a,b \in \mathbb{N}$ such that $lcm(a,b) = n$

All I have managed to prove is that:
$\frac{a}{gcd(a,b)} | n$ and $\frac{b}{gcd(a,b)} | n$

Or if $a=p_1^{a_1} \dots p_t^{a_t}, b=p_1^{b_1} \dots p_t^{b_t}, gcd(a,b) = p_1^{d_1} \dots p_t^{d_t}$ and $n = p_1^{n_1} \dots p_t^{n_t}$

Then for all $i \in \{1, \dots ,t\}$ $a_i + b_i = c_i + d_i$

2. Originally Posted by Haven
I am having troubles with this problem:

For any n find all pairs $a,b \in \mathbb{N}$ such that $lcm(a,b) = n$

All I have managed to prove is that:
$\frac{a}{gcd(a,b)} | n$ and $\frac{b}{gcd(a,b)} | n$

Or if $a=p_1^{a_1} \dots p_t^{a_t}, b=p_1^{b_1} \dots p_t^{b_t}, gcd(a,b) = p_1^{d_1} \dots p_t^{d_t}$ and $n = p_1^{n_1} \dots p_t^{n_t}$

Then for all $i \in \{1, \dots ,t\}$ $a_i + b_i = c_i + d_i$
Should the answer be in the form of an algorithm, or what?

If we have the prime factorisation of n, then we can choose pairs (a,b) based on the following:

Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$. (prime factorisation in the normal sense)

$\text{lcm}(a,b) = n \iff$

1) $a | n$ and $b | n$.

2) $\forall\ i \in \mathbb{N}, 1 \leq i \leq r,$ either $p_i^{\alpha_i} | a$ or $p_i^{\alpha_i} | b$, or both.

3. I'm sorry, the question asks, how many such pairs exist

4. It should be clarified whether (a,b) is equivalent to (b,a). For example, if n = 10, should we count (a,b) = (2,5) and (a,b) = (5,2) as distinct or not?

Are you familiar with the function that gives the number of divisors of n, commonly notated $\sigma_0(n)$? You can read more about it at MathWorld, and the way to calculate it is as the product, $\sigma_0(n)=(\alpha_1+1)\cdots(\alpha_r+1)=\prod_{ i=1}^r(\alpha_i+1)$. The reasoning behind this calculation is the same we need for our problem.

So suppose that (a,b) and (b,a) are distinct. So how many ways are there to choose the exponent of a particular $p_i$ for a and b, in order to satisfy condition (2) in my above post? It is $2\alpha_i+1$, which we can get in two ways. We can think in this way: let $p_i^{\alpha_i}$ divide a and not b. Then there are $\alpha_i$ ways to choose the exponent for b. Same in reverse. Now let $p_i^{\alpha_i}$ divide both a and b. There is only one way for this to happen. So we get $\alpha_i + \alpha_i + 1= 2\alpha_i+1$. Or we can think in this way: There are $(\alpha_i+1)^2$ ways to choose the exponents not necessarily satisfying condition (2). The ways for (2) to fail is just $\alpha_i^2$. Subtracting the second value from the first, we get the same result.

Do this for each prime and we get that the number of pairs (a,b) equals $\prod_{i=1}^r(2\alpha_i+1)$.

The answer for the non-distinct version is easily obtained from this. There is only one way to get a = b, and that's if a = b = n. So we just take half of the value above (which will always be odd) and round up.

Note that I omitted the trivial case n = 1 (which you would want to address for completeness).