Let $\phi$ be the Euler totient function and let $\tau$ count the divisors of a number. I am interested in the following question: What is the minimum and maximum of $\phi(d)\cdot\tau(n/d)$ where $d$ runs through the divisors of $n$? Is there a "nice" description in terms of $n$? Or maybe if it is easier, I am also interested in the value of the function: $f(n):= \sum_{d|n} \phi(d)^2\cdot \tau(\frac{n}{d})^2$ in terms of the prime factorization of $n$. Here is a small list in case someone recognizes the numbers:

n min max

1 1 1

2 1 2

3 2 2

4 2 3

5 2 4

6 2 4

7 2 6

8 3 4

9 3 6

10 2 8

11 2 10

12 4 6

13 2 12

14 2 12

15 4 8

16 4 8

17 2 16

18 3 12

19 2 18

20 4 12


Let $p \mid n$ be prime, $a$ its exponent in $n$ and $0\leq b \leq a$ be its exponent in $d \mid n$.

We want to know when $$f(b) :=\phi(p^b)\tau(p^{a-b}) = \begin{cases}(p-1)p^{b-1}(a-b+1) &: b >0 \\ a+1 &: b=0\end{cases}$$ is maximal and minimal.

For maximal: We have $m+1 \leq 2^m$ (*) for $m=a-b \in \mathbb N$ so $f(b) \leq f(a)$ for $b>0$. For $b=0$ we have $f(0) \leq f(a)$ unless $p=2$ and $a \in \{1,2\}$. In those cases, $f(0,1,2) = a+1, a, 2$, and the maximum is attained for $b=0$.

Conclusion: $\phi(d)\tau(n/d)$ is maximal for $d=n$ if $n$ is odd or divisible by $8$; otherwise, for $d$ equal to the odd part of $n$.

Looking more carefully at the inequalities above, we see that all values of $d$ where the maximum is attained are:

  • $n$ if $n$ is odd
  • $n, n/2$ and $n/8$ if $n$ is divisible by $8$ and no higher power of $2$
  • the odd part of $n$ if $n$ is divisible by $2$ but not $8$.

For minimal: For $0<b$ be we have $a+1 \leq 2^b(a-b+1)$ and even $a+1 \leq 2^{b-1}(a-b+1)$ unless $b=1$ (**) Hence for $p>2$, $f(b)$ is minimal for $b=0$. For $p=2$, the minimum is for $b=1$.

Conclusion: $\phi(d)\tau(n/d)$ is minimal for $d=1$ if $n$ is odd, and $d=2$ if $n$ is even.

(*) If $S$ is a set with $m$ elements, it embeds in its power set by sending each element to the corresponding singleton. There is at least one additional element in the power set: the empty set.
(**) For $0<b\leq a$, a sequence with $a$ elements embeds into a set with $2^b (a-b+1)$ elements: the latter counts for each (consecutive) subsegment of length $b$ the number of subsets of that subsegment. We can again send each element of the sequence to a singleton. There is much place left ($b-a+1$ empty sets and then some). Similarly with the exponent $2^{b-1}$, by using the inequality $b \leq 2^{b-1}$ for the last segment of length $b$ and $1 \leq 2^{b-1}$ for all others. In that case, there is again one element left unless $b=1$.

  • $\begingroup$ Thank you for your answer. The minimal part seems wrong. It would mean, that the minimum $= \tau(n)$ which seems wrong, given the empirical data. $\endgroup$ – orgesleka May 6 '18 at 7:11
  • $\begingroup$ (+1) for the maximal part. The maximal part seems to be correct as far as it concerns the empirical data. Thanks again for your answer. If it is possible to correct the part with the minimum, that would be nice. $\endgroup$ – orgesleka May 6 '18 at 7:18
  • $\begingroup$ I like the small combinatorial arguments, because they allow you to quickly prove inequalities with linear terms and powers of two, without asking a calculator and "observe" from which integer on they hold. $\endgroup$ – punctured dusk May 6 '18 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.