Show that $\frac n {\phi{(n)}}\le r+1$, where $r$ is the number of distinct prime factors of $n$. Show that $\frac n {\phi{(n)}}\le r+1$, where $r$ is the number of distinct prime factors of $n$.
I only have the idea that the $i$-th prime is $\ge i+1$ til now.
 A: We have
$$
\frac{\phi(n)}{n} = \prod_{p|n} \left( 1- \frac{1}{p} \right).$$
So,
$$
\frac{n}{\phi(n)} = \prod_{p|n} \frac{p}{p-1} \le \prod_{i=2}^{1+\omega(n)} \frac{i}{i-1} = 1+ \omega(n)$$
where $\omega(n)$ is the number of distinct prime divisors of $n$.
The idea is to replace the product over primes with a product over all integers to get the inequality, which uses your idea that the $n$-th prime is greater than or equal to $n+1$.
A: Start with $n$ such that $r=1$ (as the base case). Then, since $\phi(n)=n-1$ (because here $n$ is a prime)
$$\frac{n}{\phi(n)}=\frac{n}{n-1}\leq1+1.$$
Suppose that for $n$ with $r=i$
$$\frac{n}{\phi(n)}\leq i+1.$$
Multiplying the previous equation by $p^k$ (a new distinct prime factor to some power $k$),
$$\frac{n\;p^k}{\phi(n)}\leq (i+1)p^k,$$
and dividing by $\phi(p^k)$,
$$\frac{n\;p^k}{\phi(n)\phi(p^k)}\leq \frac{(i+1)p^k}{\phi(p^k)}.$$
To prove the iterative step, we use the fact that for $p$ a prime,
$$\phi(p^k)=p^k\left(1-\frac{1}{p}\right),$$
and the fact that $\phi$ is a multiplicative function, arriving at
$$\frac{n\;p^k}{\phi(n\;p^k)}\leq (i+1)\frac{p}{p-1}\leq (i+1)+1.$$
The very last inequality uses the fact that $p$, the $(i+1)^{\text{th}}$ prime, is $\geq (i+2)$.
