Find all positive integers $n$ such that $\phi(n) + \tau(n) > n$. How do I find all positive integers $n$ such that $\phi(n) + \tau(n) > n$? I attempted using the formulas for $\phi(n)$ and $\tau(n)$, but I feel this approach is kind of handwavy...
 A: The answer is $n = 1$, $n = 4$, or $n$ is any prime number. 
Let $S$ be the set of integers less than or equal to $n$ that are relatively prime to $n$, and let $T$ be the set of integers that are positive divisors of $n$. Then 


*

*$|S| = \phi(n)$ and $|T| = \tau(n)$, 

*$S,\,T \subseteq \{1,2, \ldots n\}$, and 

*$S \cap T = \{1\}$. 


We require $|S| + |T| > n$. By the inclusion-exclusion principle, $|S| + |T| - |S \cap T| = |S \cup T|$. We know $|S \cap T| = 1$, and by $S,\,T \subseteq \{1,2, \ldots n\}$, we have $|S \cup T| \leq n$. Therefore $|S| + |T| > n$ if and only if $|S \cup T| = n$, meaning that every positive integer in $\{1, 2, \ldots 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.
