China Western Mathematical Olympiad

We denote the set of positive divisors of $n$ by $A$, and the set of integers in the closed interval $[1,n]$ which are co-prime with $n$ by $B$. Since there is only one number $1\in A\cap B$ among $1,2,\dots ,n$, we get $d(n)+\phi (n)\le n+1$. Thus $c=0$ or $1$.

(1) If $c=0$, then $d(n)+\phi (n)=n$ implies that there exists only one number among $1,2,\dots ,n$ which is not contained in $A\cup B$. If $n$ is even, and $n>8$, then all of $n-2$ and $n-4$ are not contained in $A\cup B$.

B. In this case, $n$ does not satisfy the equation. If $n$ is odd, then when $n$ is a prime or $1$, $d(n)+\phi (n)=n+1$ (which will be discussed in case (2) below). When $n$ is a composite number, we can write $n=pq$, where $p$ and $q$ are odd and $1<p\le q$. If $q\ge 5$, then $2p$ and $4p$ are not contained in $A\cup B$, so $n$ does not satisfy the equation.

From the above discussion, we find that $$d(n)+\phi (n)=n$$ when either $n\le 8$ and $n$ is even, or $n\le 9$ and $n$ is an odd composite number. By direct verification of all the solutions of the above equation, $n$ can only be $6$, $8$ and $9$.

(2) If $c=1$, then $d(n)+\phi (n)=n+1$ implies that among $1,2,\dots ,n$ every number belongs to $A\cup B$. It is easy to find that this time $n=1$ and primes can satisfy the required condition. For the case when $n$ is even (not prime), by the same argument as above we have $n\le 4$ (consider $n-2$). If $n$ is an odd composite number, write $n=pq$, where $p$ and $q$ are odd and $3\le pq\le q$, then $2p\notin A\cup B$, a contradiction. By direct calculation we find that only $n=4$ satisfies the condition.

Therefore, the solutions of the equation $d(n)+\phi (n)=n+1$ are $n=1,4$ or primes.