For each natural number $a$ we denote $\tau (a)$ and $\phi (a)$ the number of natural numbers dividing $a$ and the number of natural numbers less than $a$ that are relatively prime to $a$. Find all natural numbers $n$ for which $n$ has exactly two different prime divisors and $n$ satisfies $\tau (\phi (n))=\phi (\tau (n))$.
Problem
Source: Bulgaria MO 2011
Tags: number theory, relatively prime, number theory proposed
jgnr
31.05.2011 04:45
Answer: $3\cdot2^{2^k-1}$ with $k\in\mathbb{N}$
Let $n=p^aq^b$, where $p,q$ are different primes ($p<q$) and $a,b\in\mathbb{N}$. So $\phi(n)=p^{a-1}q^{b-1}(p-1)(q-1)$ and $\tau(n)=(a+1)(b+1)$. We get \[{\tau(p^{a-1}q^{b-1}(p-1)(q-1))=\phi((a+1)(b+1))}\] We divide into some cases:
(1)
$p,q$ are odd.
Since $(p-1)(q-1)$ is divisible by 4, then $\tau(p^{a-1}q^{b-1}(p-1)(q-1))\ge\tau(4p^{a-1}q^{b-1})=3ab$. But $\phi((a+1)(b+1))<(a+1)(b+1)$, so $3ab<(a+1)(b+1)$, or $2ab\le a+b$, which is only possible when $a=b=1$. Now the equation becomes $\tau((p-1)(q-1))=\tau(4)$. On the other hand, $(p-1)(q-1)$ is divisible by 4, so $\tau((p-1)(q-1))\ge\tau(4)$, equality holds iff $(p-1)(q-1)=4$, therefore $p=q=3$, which contradicts the assumption that $p,q$ are different.
(2)
$p=2$, $q$ is odd.
The equation becomes \[\tau(2^{a-1}q^{b-1}(q-1))=\phi((a+1)(b+1))\] Since $(a+1)(b+1)$ is clearly not a prime, then $\phi((a+1)(b+1))\le\frac{(a+1)(b+1)}2$. We also have $\tau(2^{a-1}q^{b-1}(q-1))>\tau(2^{a-1}q^{b-1})=ab$. So $\frac{(a+1)(b+1)}2>ab$, or $(a-1)(b-1)<2$. Hence we have the following subcases:
(2.1)
$a=b=2$
The equation becomes $\tau(2q(q-1))=\phi(9)$. But $\tau(2q(q-1))>\tau(2q)=4$ and $\phi(9)=3$, we get a contradiction.
(2.2)
$a=1$
The equation becomes $\tau(q^{b-1}(q-1))=\phi(2(b+1))$. But $\phi(2(b+1))\le b+1$ and $\tau(q^{b-1}(q-1))\ge\tau(2q^{b-1})=2b$, so $b+1\le 2b$. The only possibility is $b=1$, equality must hold everywhere, hence $q^{b-1}(q-1)=2q^{b-1}$, which gives $q=3$. Therefore $n=2^13^1=6$, which is indeed a solution.
(2.3)
$b=1$
The equation becomes $\tau(2^{a-1}(q-1))=\phi(2(a+1))$. Suppose $q>3$. If $q-1$ is divisible by 4, then $\tau(2^{a-1}(q-1))\ge\tau(2^{a+1})=a+2$, but $\phi(2(a+1))\le a+1$, a contradiction. If $q-1$ is not divisible by 4, then it has an odd prime divisor $r$, therefore $\tau(2^{a-1}(q-1))\ge\tau(2^ar)=2(a+1)$, hence $\phi(2(a+1))\ge2(a+1)$, which is impossible. Now suppose $q=3$, then $\tau(2^a)=\phi(2(a+1))$, so $a+1=\phi(2(a+1))$, which implies that $2(a+1)$ is a power of 2. Hence $a=2^k-1$, and we get $n=2^{2^k-1}3$, which is indeed another solution. Also note that the previous answer is also of this form: $2^{2^1-1}3=6$.
Edit: This solution contains some mistakes, I thought that $\phi(n)\le\frac{n}2$ if $n$ is composite, which is wrong.
mahanmath
31.05.2011 17:39
Answers are $3^{q-1} . 2 ^{q^k -1}$ for all prime $q$ and $ k\in\mathbb{N} $ .
Put $n= 2^a . p^b$ and $p-1= t .2^m$ ($ 2 \nmid t$ ) Then the equation becomes :
$b (a+m) \tau(t) = \phi ((a+1)(b+1)) = (a+1)(b+1) \prod_{p \mid (a+1)(b+1)}^{ } (1- \frac{1}{p})$ (#)
Now if $b+1$ has a proper prime divisor like $r$ (i.e $r < b+1$ and $r \mid b+1$) then
$(1- \frac{1}{r})(b+1) < b$ but in this case the RHS can`t reach the LHS in (#).
Hence $b+1$ is prime . So in product $\prod_{p \mid (a+1)(b+1)}^{ } (1- \frac{1}{p})$
one of the fraction is $1- \frac{1}{b+1}$ .So after clear $b, b+1$ from both sides with $1- \frac{1}{b+1}$
(#) boils down to :
$(a+m) \tau(t) = (a+1) \prod_{p \mid (a+1) , p \neq b+1 }^{ } (1- \frac{1}{p})$
But It immediately implies $a+1 $ has no prime divisor except $b+1$
(because $\prod_{p \mid (a+1) , p \neq b+1 }^{ } (1- \frac{1}{p}) <1$ but $m \geq 1$ )
So $m=t=1$
It leaves us with the case $p=3$ , $b=q-1$ and $a = q^k -1$ (for some prime $q$ ) and it`s easy to see they work .