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.

Printable View

- Jun 1st 2010, 06:18 PMmeleseIs 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 PMchiph588@
- Jun 1st 2010, 06:29 PMBruno J.
You probably mean $\displaystyle \tau(mn)=\tau(m)\tau(n)$?

- Jun 1st 2010, 06:30 PMBruno J.
- Jun 1st 2010, 06:46 PMchiph588@
Too slow (Wink)

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 PMBruno 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 AMmelese
yes I do, I wrote that early in the morning...

- Jun 2nd 2010, 06:44 AMmeleseI 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 AMchiph588@
- Jun 3rd 2010, 05:23 AMmelese
Again, you corrected me. Thank you so much for your help!