# values of $n$ for which $\varphi(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\}$

• $\varphi$ denotes the Euler phi function

• $\tau$ denotes the divisor function

• $\mid$ denotes divides

• $\|$ denotes exactly divides

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

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

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

Note that $\gamma$ is a multiplicative function since both $\varphi$ 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.

$\begin{array}[]{ccccc}\gamma(1)&=&\displaystyle\frac{1}{1}&=&1\\ \\ \gamma(2)&=&\displaystyle\frac{2}{1}&=&2\\ \\ \gamma(4)&=&\displaystyle\frac{3}{2}\\ \\ \gamma(8)&=&\displaystyle\frac{4}{4}&=&1\\ \\ \gamma(16)&=&\displaystyle\frac{5}{8}\\ \\ \gamma(32)&=&\displaystyle\frac{6}{16}&=&\displaystyle\frac{3}{8}\\ \\ \\ \gamma(3)&=&\displaystyle\frac{2}{2}&=&1\\ \\ \gamma(9)&=&\displaystyle\frac{3}{6}&=&\displaystyle\frac{1}{2}\\ \\ \\ \gamma(5)&=&\displaystyle\frac{2}{4}&=&\displaystyle\frac{1}{2}\end{array}$

Note that

$\begin{array}[]{rl}\gamma(p^{k})&=\displaystyle\frac{\tau(p^{k})}{\varphi(p^{k% })}\\ \\ &=\displaystyle\frac{k+1}{p^{k-1}(p-1)}.\end{array}$

If $p$ is fixed, we can extend this to a continuous function $\Gamma_{p}\colon\mathbb{R}\to\mathbb{R}$ defined by

 $\Gamma_{p}(x)=\frac{x+1}{p^{x-1}(p-1)}.$

We investigate the derivative (http://planetmath.org/Derivative) of $\Gamma_{p}$ for $x\geq 1$:

$\begin{array}[]{rl}{\Gamma_{p}}^{\prime}(x)&=\displaystyle\frac{1}{p-1}\cdot% \frac{p^{x-1}-(x+1)p^{x-1}\ln p}{(p^{x-1})^{2}}\\ \\ &=\displaystyle\frac{1-(x+1)\ln p}{p^{x-1}(p-1)}\\ \\ &<\displaystyle\frac{1-2\ln 2}{p^{x-1}(p-1)}\\ \\ &<0.\end{array}$

Thus, for $p$ fixed and $k\geq 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}\notin\{1,2,3,4,8,16\}$. Then

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

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

This lemma has an immediate consequence:

###### Lemma 2.

Let $m$ be an odd natural number. Then

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

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

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

Suppose that $4\|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\not\|n$.

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

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

Therefore,

 $\gamma(m)\geq\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\|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}\|m$ with $k>0$,

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

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

• Case III: $2\|n$ and $3\|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}\|m$ with $k>0$,

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

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

• Case IV: $2\|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\geq 2$ and

 $1=\gamma(n)=\gamma(2\cdot 3^{k}m)=\gamma(2)\gamma(3^{k})\gamma(m)=2\gamma(3^{k% })\gamma(m)\leq 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}:\varphi(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.

Title values of $n$ for which $\varphi(n)=\tau(n)$ ValuesOfNForWhichvarphintaun 2013-03-22 18:03:48 2013-03-22 18:03:48 Wkbj79 (1863) Wkbj79 (1863) 12 Wkbj79 (1863) Feature msc 11A25 EulerPhifunction TauFunction