Results 1 to 4 of 4

Math Help - 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 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
    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 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.
    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 \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).
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum