Results 1 to 4 of 4

Thread: LCM

  1. #1
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8

    LCM

    I am having troubles with this problem:

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

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

    Or if $\displaystyle 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 $\displaystyle n = p_1^{n_1} \dots p_t^{n_t}$

    Then for all $\displaystyle i \in \{1, \dots ,t\}$ $\displaystyle a_i + b_i = c_i + d_i$
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Haven View Post
    I am having troubles with this problem:

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

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

    Or if $\displaystyle 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 $\displaystyle n = p_1^{n_1} \dots p_t^{n_t}$

    Then for all $\displaystyle i \in \{1, \dots ,t\}$ $\displaystyle 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 $\displaystyle n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$. (prime factorisation in the normal sense)

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

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

    2) $\displaystyle \forall\ i \in \mathbb{N}, 1 \leq i \leq r,$ either $\displaystyle p_i^{\alpha_i} | a$ or $\displaystyle p_i^{\alpha_i} | b$, or both.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8
    I'm sorry, the question asks, how many such pairs exist
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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 $\displaystyle \sigma_0(n)$? You can read more about it at MathWorld, and the way to calculate it is as the product, $\displaystyle \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 $\displaystyle p_i$ for a and b, in order to satisfy condition (2) in my above post? It is $\displaystyle 2\alpha_i+1$, which we can get in two ways. We can think in this way: let $\displaystyle p_i^{\alpha_i}$ divide a and not b. Then there are $\displaystyle \alpha_i$ ways to choose the exponent for b. Same in reverse. Now let $\displaystyle p_i^{\alpha_i}$ divide both a and b. There is only one way for this to happen. So we get $\displaystyle \alpha_i + \alpha_i + 1= 2\alpha_i+1$. Or we can think in this way: There are $\displaystyle (\alpha_i+1)^2$ ways to choose the exponents not necessarily satisfying condition (2). The ways for (2) to fail is just $\displaystyle \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 $\displaystyle \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).
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum