values of $n$ for which $\phi (n)=\tau (n)$

Within this entry, we use the following notation:

• $\mathbb{N}$ denotes the natural numbers (positive integers)

• $n\in \mathbb{N}$

• $p$ denotes a prime

• $k\in \mathbb{N}\cup \{0\}$

• $\phi$ denotes the Euler phi function

• $\tau$ denotes the divisor function

• $\mid$ denotes divides

• $\parallel$ denotes exactly divides

Within this entry, we will determine all values of $n$ for which $\phi (n)=\tau (n)$.

Define $\gamma :\mathbb{N}\to \mathbb{Q}$ by

$$\gamma (n)=\frac{\tau (n)}{\phi (n)}.$$

Note that $\gamma$ is a multiplicative function since both $\phi$ and $\tau$ are. Thus, we will initially focus on the values of $\gamma$ at prime powers. We will need specific values of $\gamma (p^k)$. These are calculated below.

Note that

If $p$ is fixed, we can extend this to a continuous function ${\mathrm{\Gamma }}_p:ℝ\to ℝ$ defined by

$${\mathrm{\Gamma }}_p(x)=\frac{x+1}{p^{x-1}(p-1)}.$$

We investigate the derivative (http://planetmath.org/Derivative) of ${\mathrm{\Gamma }}_p$ for $x\ge 1$:

Thus, for $p$ fixed and $k\ge 1$, $\gamma (p^k)$ is a strictly decreasing function of $k$.

On the other hand, from the equation

$$\gamma (p^k)=\frac{k+1}{p^{k-1}(p-1)},$$

it is clear that, if $k$ is fixed, $\gamma (p^k)$ is a strictly decreasing function of $p$.

Thus, we have proven the following:

Lemma 1.

Let $p$ be a prime and $k$ be a nonnegative integer with $p^k\mathrm{\notin }\mathrm{\{}\mathrm{1}\mathrm{,}\mathrm{2}\mathrm{,}\mathrm{3}\mathrm{,}\mathrm{4}\mathrm{,}\mathrm{8}\mathrm{,}\mathrm{16}\mathrm{\}}$. Then

$$\gamma (p^k)\le \frac{1}{2}$$

with equality holding if and only if $p^k\mathrm{\in }\mathrm{\{}\mathrm{5}\mathrm{,}\mathrm{9}\mathrm{\}}$.

This lemma has an immediate consequence:

Lemma 2.

Let $m$ be an odd natural number. Then

$$\gamma (m)=1\mathit{\text{ or }}\gamma (m)\le \frac{1}{2}.$$

Moreover, $\gamma \mathit{}\mathrm{(}m\mathrm{)}\mathrm{=}\mathrm{1}$ if and only if $m\mathrm{=}\mathrm{1}$ or $m\mathrm{=}\mathrm{3}$.

Now we will examine the general case. Let $\phi (n)=\tau (n)$. Then $\gamma (n)=1$.

Suppose that $4\parallel n$. Let $m$ be an odd natural number with $n=4m$. Thus,

$$1=\gamma (n)=\gamma (4m)=\gamma (4)\gamma (m)=\frac{3}{2}\gamma (m).$$

Therefore,

$$\gamma (m)=\frac{2}{3},$$

which contradicts the second lemma. Hence, $4\parallel ̸n$.

Suppose that $16\mid n$. Let $m$ be an odd natural number with $n=2^{k}m$. Then $k\ge 4$. Thus,

$$1=\gamma (n)=\gamma (2^{k}m)=\gamma (2^k)\gamma (m)\le \gamma (16)\gamma (m)=\frac{5}{8}\gamma (m).$$

Therefore,

$$\gamma (m)\ge \frac{8}{5},$$

which contradicts the second lemma. Hence, $16\nmid n$.

Now we deal with the cases that can actually occur.

• Case I: $n$ is odd

  The second lemma immediately applies, yielding $n=1$ or $n=3$.

• Case II: $2\parallel n$ and $3\nmid n$

  Let $m$ be an odd natural number with $n=2m$. Then $3\nmid m$ and

  $$1=\gamma (n)=\gamma (2m)=\gamma (2)\gamma (m)=2\gamma (m).$$

  Thus,

  $$\gamma (m)=\frac{1}{2}.$$

  By the first lemma, for all $p^k\parallel m$ with $k>0$,

  $$\gamma (p^k)\le \frac{1}{2}$$

  with equality holding if and only if $p^k=5$. Therefore, $m=5$. Hence $n=10$.

• Case III: $2\parallel n$ and $3\parallel n$

  Let $m$ be an odd natural number with $n=6m$. Then $3\nmid m$ and

  $$1=\gamma (n)=\gamma (6m)=\gamma (2)\gamma (3)\gamma (m)=2\gamma (m).$$

  Thus,

  $$\gamma (m)=\frac{1}{2}.$$

  By the first lemma, for all $p^k\parallel m$ with $k>0$,

  $$\gamma (p^k)\le \frac{1}{2}$$

  with equality holding if and only if $p^k=5$. Therefore, $m=5$. Hence $n=30$.

• Case IV: $2\parallel n$ and $9\mid n$

  Let $m$ be an odd natural number with $3\nmid m$ such that $n=2\cdot 3^{k}m$. Then $k\ge 2$ and

  $$1=\gamma (n)=\gamma (2\cdot 3^{k}m)=\gamma (2)\gamma (3^k)\gamma (m)=2\gamma (3^k)\gamma (m)\le 2\gamma (9)\gamma (m)=\gamma (m).$$

  Since $3\nmid m$, the second lemma yields that $m=1$. Thus,

  $$1=\gamma (n)=\gamma (2\cdot 3^k)=\gamma (2)\gamma (3^k)=2\gamma (3^k).$$

  Therefore,

  $$\gamma (3^k)=\frac{1}{2}.$$

  By the first lemma, $k=2$. Hence, $n=18$.

• Case V: $8\mid n$

  Recall that $16\nmid n$. Thus, there exists an odd natural number $m$ with $n=8m$. Then

  $$1=\gamma (n)=\gamma (8m)=\gamma (8)\gamma (m)=\gamma (m).$$

  The second lemma yields that $m=1$ or $m=3$. Hence, $n=8$ or $n=24$.

It follows that

$$\{n\in \mathbb{N}:\phi (n)=\tau (n)\}=\{1,3,8,10,18,24,30\}.$$

This list of numbers appears in the OEIS as sequence http://www.research.att.com/ njas/sequences/A020488A020488.