prove that tau(n) + phi(n)

Question

prove that tau(n) + phi(n) <= n + 1 for all positive integers n

kinggeorge · Answer

Well, tau(n) is the number of divisors of n, and phi(n) is the number of numbers less than n coprime to n. The most straightforward way to prove this, would be from the formulas in my opinion.

anonymous · Answer

$\tau(n)$ is divisors function?

anonymous · Answer

ah ok @KingGeorge

kinggeorge · Answer

On second thought, that way probably leads to complicated things happening.

anonymous · Answer

@jfluth consider the positive integers less than or equal to $n$. $\tau(n)$ counts the number of these that are divisors of $n$; the rest are not. of the rest, consider some are actually relatively prime to $n$ -- this is what $\varphi(n)$ counts. for some $n$ there are numbers less than $n$ that are neither relatively prime nor divisors, hence it only makes sense for $\tau(n)+\varphi(n)\le n+1$

kinggeorge · Answer

That's the much simpler and easier way than going from the formulas :P

anonymous · Answer

e.g. $n=p_1^ap_2^bp_3^c\cdots$ for prime $p_i$ we may have another smaller number $m=p_1q$ for some other prime $q$; it is clearly not relatively prime and yet it is still not a proper divisor. clearly $\tau(n)+\varphi(n)$ cannot always account for all the numbers up to $n$, then

kinggeorge · Answer

And in general, you will only have equality when $n$ is 1 or prime.

anonymous · Answer

P.S. the reason for the $+1$ is that both $\tau(n),\varphi(n)$ count $1$ :-p

kinggeorge · Answer

Although you also have equality with 4, but that's a special case.

anonymous · Answer

yes @KingGeorge ofc because $4$ is the first composite number!