Saudi Arabia Mathematical Competitions 2012

The answer is $n=1$, $n=4$, or $n$ is any prime number. Let $S$ be the set of integers less than $n$ and relatively prime to $n$, and let $T$ be the set of integers that are positive divisors of $n$. Then $$(i)|S|=\varphi (n)\text{ and }|T|=\tau (n),$$ $$(ii)S,T\subseteq \{1,2,\dots ,n\},\text{ and}$$ $$(iii)S\cap T=\{1\}.$$ We require $|S|+|T|>n$. By the principle of inclusion-exclusion, $|S|+|T|-|S\cap T|=|S\cup T|$. We know $|S\cap T|=1$, and by $S,T\subseteq \{1,2,\dots ,n\}$, we have $|S\cup T|\le n$. Therefore $|S|+|T|>n$ if and only if $|S\cup T|=n$, meaning that every positive integer in $\{1,2,\dots ,n\}$ is either relatively prime to $n$ or a divisor of $n$. It is easy to check that this is true for $n=1$, $n$ prime, and $n=4$. Now suppose $n$ is a composite number.

Let $d$ be the smallest divisor of $n$ greater than $1$. $d<n$ since $n$ is not prime. Consider $n-d$. We have $\gcd (n-d,n)=d>1$, so $n-d$ must be a divisor of $n$. But $n=kd$ for some $k$, so if $n-d$ divides $n$ then we have an $m$ such that $m(kd-d)=kd$. This gives $m(k-1)=k$. This is only possible for $k=2$, so $n=2d$.

Then since $n$ is even, $2$ is the smallest divisor of $n$ greater than $1$ and $d=2$. Therefore $n=4$, and this is the only composite number that works.