# Is the converse statement true?

• Jun 1st 2010, 06:18 PM
melese
Is the converse statement true?
Let $\displaystyle m,n$ be natural numbers.
Does $\displaystyle \tau(mn)=\tau(m)\tau(n)$
, where $\displaystyle \tau(k)$ is number of positive divisors of k, implies that
$\displaystyle \gcd(m,n)=1$?

Thanks.
• Jun 1st 2010, 06:27 PM
chiph588@
Quote:

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

Thanks.

Since your title says converse, I assume you meant to say $\displaystyle \tau(mn)=\tau(m)\tau(n)$?
• Jun 1st 2010, 06:29 PM
Bruno J.
You probably mean $\displaystyle \tau(mn)=\tau(m)\tau(n)$?
• Jun 1st 2010, 06:30 PM
Bruno J.
Quote:

Originally Posted by chiph588@
Since your title says converse, I assume you meant to say $\displaystyle \tau(mn)=\tau(m)\tau(n)$?

Too fast (Talking)
• Jun 1st 2010, 06:46 PM
chiph588@
Quote:

Originally Posted by Bruno J.
Too fast (Talking)

Too slow (Wink)

Quote:

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

Thanks.

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

Here's some reasoning:

Suppose $\displaystyle mn=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ and $\displaystyle m=p_1^{a_1}p_2^{a_2}\cdots p_i^{b_i}\cdots p_j^{b_j}$ and $\displaystyle 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}$.

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

Omitting the simplification we get $\displaystyle \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 $\displaystyle b_r>0\implies a_r+1<b_r(a_r-b_r)+a_s+1$, so we're forced to have $\displaystyle b_s=0 \; \forall \; s$ if we want this equality to hold.
• Jun 1st 2010, 08:27 PM
Bruno J.
If you prove it, then it's true! (Happy)

Here's a less computational argument. Let $\displaystyle D_n$ denote the set of divisors of $\displaystyle n$, and suppose that $\displaystyle g=(m,n)>1$. I exhibit a surjection $\displaystyle f : \ D_m \times D_n \to D_{mn}$ which is not an injection. For every $\displaystyle (u,v) \in D_m \times D_n$, let $\displaystyle f(u,v)=uv$. This map is clearly a surjection. But $\displaystyle f(m/g,n)=f(m,n/g)$. Therefore $\displaystyle |D_m\times D_n|>|D_{mn}|$.
• Jun 2nd 2010, 06:33 AM
melese
yes I do, I wrote that early in the morning...
• Jun 2nd 2010, 06:44 AM
melese
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:
$\displaystyle m=p_1^{m_1}p_2^{m_2}\dots p_r^{m_r}$ and $\displaystyle n=p_1^{n_1}p_2^{n_2}\dots p_r^{n_r}$, where for $\displaystyle 1\leq i\leq r$ $\displaystyle m_i$ and $\displaystyle n_i$ are nonnegative. Also, for any prime $\displaystyle p_i$, $\displaystyle p_i$ divides at leat one of $\displaystyle m$ and $\displaystyle n$.

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

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

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

Is my argument right? Thanks for your help.
• Jun 2nd 2010, 10:50 AM
chiph588@
Quote:

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

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

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

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

Is my argument right? Thanks for your help.

You mean $\displaystyle m_in_i+m_i+n_i+1\geq m_i+n_i+1$.

Other than that, it looks fine to me.
• Jun 3rd 2010, 05:23 AM
melese
Again, you corrected me. Thank you so much for your help!