I would like to find some upper bound on $\frac{n}{|Z_n^*|}$ i.e. to show that many of the elements in $Z_n$ are also in $Z_n^*$. I want to show that $\frac{n}{|Z_n^*|}=O(log^cn)$ for some $c \in N$. Of course, it is possible to assume that $n>k$ for any desired predefined $k \in N$.
The following is not mandatory to read in order to answer the question:
Why am I interested in such result? I wish to find $x \sim U(Z_n^*)$ (random uniformly distributed element in $Z_n^*$) in the following method:
- Choose $x \sim U(Z_n)$
- if $x \in Z_n^*$ finish; else return to 1 (try again)
It is a legitimate way to choose $x \sim U(Z_n^*)$, I only wish to bound the expectation of number of tries it takes to obtain $x$, lets denote it by $t$. Of course, $t \sim Geo(\frac{|Z_n^*|}{n})$ so that $E[t]= \frac{n}{|Z_n^*|}$. So $\frac{n}{|Z_n^*|}=O(log^cn)$ (for some $c \in N$) gives me very nice bound on $E[t]$.
Thanks!
Theorem: $n/\varphi(n)$ is unbounded.
Proof: if $n = \prod_{p<m} p$, then $\varphi(n)/n = \prod \frac{p-1}{p} = \prod (1-\frac{1}p)$.
So $n/\varphi(n) = \prod (1-\frac{1}p)^{-1}$. This is the partial product expansion for $\zeta(1)$. As $m\to \infty$, the product approaches $\zeta(1) = \infty$. (This is not completely rigorous, but the claim is true. Or, you can think of $\varphi(n)/n$ as the proportion of integers not divisible by any $p<m$ - it's clear that it tends to $0$ as $m \to \infty$.)
More precisely, we have the following theorem of Mertens:
$$\lim_{n \to \infty}\log n \prod_{p \leq n}(1-1/p) = e^{-\gamma}, $$
where $\gamma$ is the Euler-Mascheroni constant. You can certainly use this to find a bound for $n/\varphi(n)$.