Japan Mathematical Olympiad

Let ${\prod }_{i=1}^m{x}_i$ denote the product of $m$ real numbers $x_1,x_2,\dots ,x_m$. For any positive integer $N$, let ${\text{ord}}_{2}N$ denote the maximum nonnegative integer $\ell$ such that $2^{\ell }$ divides $N$.

$n=1$ does not meet the assumption since $\frac{1^{\varphi (1)}-1}{d(1{)}^5}=0$ is an integer. In the following we assume $n\ge 2$. If distinct prime numbers $p_1,p_2,\dots ,p_k$ and positive integers $e_1,e_2,\dots ,e_k$ satisfy $n={\prod }_{i=1}^k{p}_i^{e_i}$, then $\varphi (n)={\prod }_{i=1}^k{p}_i^{e_i-1}(p_i-1)$.

When $n$ is even, the assumption that $\frac{\varphi (n{)}^{d(n)}+1}{n}$ is an integer implies that $\varphi (n)$ is odd, thus $n=2$. On the other hand, $n=2$ satisfies the assumptions since $\frac{\varphi (2{)}^{d(2)}+1}{2}=\frac{1^2+1}{2}=1$ and $\frac{2^{\varphi (2)}-1}{d(2{)}^5}=\frac{2^1-1}{2^5}=\frac{1}{32}$.

In the following we assume $n$ is odd and $n\ge 3$. The assumption that $\frac{\varphi (n{)}^{d(n)}+1}{n}$ is an integer implies that $n$ and $\varphi (n)$ are coprime, thus $n$ is square-free. Then $n={\prod }_{i=1}^k{p}_i$ with distinct odd primes $p_1,\dots ,p_k$, thus $d(n)=2^k$. Now we need the following lemma.

Lemma. For any odd integer $x\ge 3$ and any positive integer $y$, there holds ${\text{ord}}_2(x^y-1)\ge {\text{ord}}_2(x-1)+{\text{ord}}_{2}y$.

Proof. Suppose $y=2^v\cdot s$ with a nonnegative integer $v$ and a positive odd integer $s$. Then $x^y-1=(x^s-1){\prod }_{i=0}^{v-1}(x^{2^i\cdot s}+1)$. Since $x^s-1=(x-1)(x^{s-1}+\cdots +x+1)$, ${\text{ord}}_2(x^s-1)\ge {\text{ord}}_2(x-1)$. Also, ${\text{ord}}_2(x^{2^i\cdot s}+1)\ge 1$ for any $i$ since $x$ is odd, thus we obtain ${\text{ord}}_2\left({\prod }_{i=0}^{v-1}(x^{2^i\cdot s}+1)\right)\ge v$. Hence ${\text{ord}}_2(x^y-1)\ge {\text{ord}}_2(x-1)+{\text{ord}}_{2}y$. $■$

The condition that $\frac{n^{\varphi (n)}-1}{d(n{)}^5}=\frac{n^{\varphi (n)}-1}{2^{5k}}$ is not an integer is equivalent to ${\text{ord}}_2(n^{\varphi (n)}-1)<5k$. The above lemma implies that ${\text{ord}}_2(n^{\varphi (n)}-1)\ge {\text{ord}}_2(n-1)+{\text{ord}}_2(\varphi (n))$. Since $\frac{\varphi (n{)}^{d(n)}+1}{n}$ is an integer, for any $p_i$ there holds $\varphi (n{)}^{2k}\equiv -1(\mathrm{mod}{p}_i)$, thus $\varphi (n{)}^{2^{k+1}}\equiv 1(\mathrm{mod}{p}_i)$. Let $t_i$ be the minimum positive integer $t$ such that $\varphi (n{)}^t\equiv 1(\mathrm{mod}{p}_i)$. If a positive integer $\ell$ satisfies $\varphi (n{)}^{\ell }\equiv 1(\mathrm{mod}{p}_i)$, then $t_i$ divides $\ell$; this is because when $r$ denotes the remainder of $\ell$ modulo $t_i$, then $\varphi (n{)}^{\ell }\equiv \varphi (n{)}^r\equiv 1(\mathrm{mod}{p}_i)$, which implies $r=0$ by the minimality of $t_i$. Now $t_i$ divides $2^{k+1}$ since $\varphi (n{)}^{2^{k+1}}\equiv 1(\mathrm{mod}{p}_i)$. On the other hand $t_i$ does not divide $2^k$ since $\varphi (n{)}^{2^k}\equiv -1\not\equiv 1(\mathrm{mod}{p}_i)$. Hence we obtain $t_i=2^{k+1}$.

By the Fermat's little theorem $\varphi (n{)}^{p_i-1}\equiv 1(\mathrm{mod}{p}_i)$, thus $2^{k+1}$ divides $p_i-1$. Hence ${\text{ord}}_2(\varphi (n))={\sum }_{i=1}^k{\text{ord}}_2(p_i-1)\ge k(k+1)$. On the other hand, by $n-1={\prod }_{i=1}^k{p}_i-1\equiv {\prod }_{i=1}^{k}1-1\equiv 0(\mathrm{mod}{2}^{k+1})$ we obtain ${\text{ord}}_2(n-1)\ge k+1$. Therefore $5k>{\text{ord}}_2(n^{\varphi (n)}-1)\ge {\text{ord}}_2(n-1)+{\text{ord}}_2(\varphi (n))\ge (k+1{)}^2$. Then we obtain $k=1,2$.

When $k=1$ we obtain $\varphi (n)=n-1$ and $d(n)=2$, thus $\frac{\varphi (n{)}^{d(n)}+1}{n}=\frac{(n-1{)}^2+1}{n}=n-2+\frac{2}{n}$ is not an integer, which contradicts the assumption. When $k=2$, the condition $3+2\cdot 3\le {\text{ord}}_2(n-1)+{\text{ord}}_2(\varphi (n))<5\cdot 2$ implies that ${\text{ord}}_2(n-1)=3$ and ${\text{ord}}_2(\varphi (n))=6$. Since $p_1-1$ and $p_2-1$ are both multiples of $2^{2+1}$, ${\text{ord}}_2((p_1-1)(p_2-1))={\text{ord}}_2(\varphi (n))=6$ implies ${\text{ord}}_2(p_1-1)={\text{ord}}_2(p_2-1)=3$. Thus $p_1\equiv p_2\equiv 9(\mathrm{mod}16)$. Hence $n-1=p_1{p}_2-1\equiv 0$ (mod 16), which contradicts $or{d}_2(n-1)=3$. Thus there does not exist an odd integer $n\ge 3$ which satisfies the required conditions.

Hence the answer is $n=2$.