Results 1 to 10 of 10

Math Help - Is the converse statement true?

  1. #1
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148

    Is the converse statement true?

    Let m,n be natural numbers.
    Does \tau(mn)=\tau(m)\tau(n)
    , where  \tau(k) is number of positive divisors of k, implies that
    \gcd(m,n)=1?

    Thanks.
    Last edited by melese; June 2nd 2010 at 07:37 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by melese View Post
    Let m,n be natural numbers.
    Does \tau(mn)=mn
    , where  \tau(k) is number of positive divisors of k, implies that
    \gcd(m,n)=1?

    Thanks.
    Since your title says converse, I assume you meant to say  \tau(mn)=\tau(m)\tau(n) ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    You probably mean \tau(mn)=\tau(m)\tau(n)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by chiph588@ View Post
    Since your title says converse, I assume you meant to say  \tau(mn)=\tau(m)\tau(n) ?
    Too fast
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Bruno J. View Post
    Too fast
    Too slow

    Quote Originally Posted by melese View Post
    Let m,n be natural numbers.
    Does \tau(mn)=mn
    , where  \tau(k) is number of positive divisors of k, implies that
    \gcd(m,n)=1?

    Thanks.
    Correct me if I'm wrong anyone but I think it might be true...

    Here's some reasoning:

    Suppose  mn=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} and  m=p_1^{a_1}p_2^{a_2}\cdots p_i^{b_i}\cdots p_j^{b_j} and  n=p_i^{a_i-b_i}\cdots p_j^{a_j-b_j}p_{j+1}^{a_{j+1}}\cdots p_k^{a_k} .

     \tau(mn)=\prod_{s=1}^k (a_s+1) = \tau(m)\tau(n)

    Omitting the simplification we get  \prod_{s=i}^j (a_s+1)=\prod_{s=i}^j (b_s+1)(a_s-b_s+1) = \prod_{s=i}^j (b_s(a_s-b_s)+a_s+1)

    But  b_r>0\implies a_r+1<b_r(a_r-b_r)+a_s+1 , so we're forced to have  b_s=0 \; \forall \; s if we want this equality to hold.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    If you prove it, then it's true!

    Here's a less computational argument. Let D_n denote the set of divisors of n, and suppose that g=(m,n)>1. I exhibit a surjection f : \ D_m \times D_n \to D_{mn} which is not an injection. For every (u,v) \in D_m \times D_n, let f(u,v)=uv. This map is clearly a surjection. But f(m/g,n)=f(m,n/g). Therefore |D_m\times D_n|>|D_{mn}|.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    yes I do, I wrote that early in the morning...
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148

    I have an argument but I'm not sure...

    Allowing the exponents to be zero, if necessary, we can write the following (similar) prime factorizations:
    m=p_1^{m_1}p_2^{m_2}\dots p_r^{m_r} and n=p_1^{n_1}p_2^{n_2}\dots p_r^{n_r}, where for 1\leq i\leq r m_i and n_i are nonnegative. Also, for any prime p_i, p_i divides at leat one of m and n.

    Now, mn=p_1^{m_1+n_1}p_2^{m_2+n_2}\dots p_r^{m_r+n_r} and then \tau(mn)=(m_1+n_1+1)(m_2+n_2+1)\dots (m_r+n_r+1).
    Computing \tau(m)\tau(n) gives \tau(m)\tau(n)=(m_1+1)(n_1+1)\dots... (m_r+1)(n_r+1) =(m_1n_1+m_1+n_1+1)\dots (m_rn_r+m_r+n_r+1).

    Now comes my difficulty...
    For each i=1,2,\dots ,r, m_in_i+m_i+n_i+1\leq m_i+n_i+1, so if we want \tau(mn)=\tau(m)\tau(n) we must have
    m_in_i+m_i+n_i+1= m_i+n_i+1 for i=1,2,\dots ,r. Otherwise \tau(mn)<\tau(m)\tau(n).

    But then m_in_i=0. Without loss of generality m_i=0 and this means that p_i divides n but not m. In this manner m and n are relatively prime.
    By the way exactly one of m_i and n_i equals 0 due to: "for any prime p_i, p_idivides at leat one of m and n."

    Is my argument right? Thanks for your help.
    Last edited by melese; June 2nd 2010 at 09:06 AM. Reason: I scribled to see if I can re-edit.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by melese View Post
    Allowing the exponents to be zero, if necessary, we can write the following (similar) prime factorizations:
    m=p_1^{m_1}p_2^{m_2}\dots p_r^{m_r} and n=p_1^{n_1}p_2^{n_2}\dots p_r^{n_r}, where for 1\leq i\leq r m_i and n_i are nonnegative. Also, for any prime p_i, p_i divides at leat one of m and n.

    Now, mn=p_1^{m_1+n_1}p_2^{m_2+n_2}\dots p_r^{m_r+n_r} and then \tau(mn)=(m_1+n_1+1)(m_2+n_2+1)\dots (m_r+n_r+1).
    Computing \tau(m)\tau(n) gives \tau(m)\tau(n)=(m_1+1)(n_1+1)\dots... (m_r+1)(n_r+1) =(m_1n_1+m_1+n_1+1)\dots (m_rn_r+m_r+n_r+1).

    Now comes my difficulty...
    For each i=1,2,\dots ,r, m_in_i+m_i+n_i+1\leq m_i+n_i+1, so if we want \tau(mn)=\tau(m)\tau(n) we must have
    m_in_i+m_i+n_i+1= m_i+n_i+1 for i=1,2,\dots ,r. Otherwise \tau(mn)<\tau(m)\tau(n).

    But then m_in_i=0. Without loss of generality m_i=0 and this means that p_i divides n but not m. In this manner m and n are relatively prime.
    By the way exactly one of m_i and n_i equals 0 due to: "for any prime p_i, p_idivides at leat one of m and n."

    Is my argument right? Thanks for your help.
    You mean m_in_i+m_i+n_i+1\geq m_i+n_i+1.

    Other than that, it looks fine to me.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Again, you corrected me. Thank you so much for your help!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Where is this statement true?
    Posted in the Calculus Forum
    Replies: 3
    Last Post: October 21st 2011, 12:42 PM
  2. Set theory. Is the converse true?
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: June 10th 2011, 11:22 AM
  3. True implication whose converse is false
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 23rd 2011, 06:03 AM
  4. Finding the Converse & Contrapositive of a Statement
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: October 11th 2008, 02:00 PM
  5. true statement
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: July 28th 2006, 12:16 AM

/mathhelpforum @mathhelpforum