# Comparing $\phi(\phi(n))$ and the number of elements in $(\mathbb{Z}/\phi(n)\mathbb{Z})^{\times}$ of order $\le \log(n)$

First notice that $\mid (\mathbb{Z}/\phi(n)\mathbb{Z})^{\times}\mid=\phi(\phi(n))$

Now if $n=p_1^{a_1}...p_k^{a_k}$ then $\phi(n)=p_1^{a_1-1}(p_1-1)...p_k^{a_k-1}(p_k-1)$ with the $p_i \ge 2$ distinct prime and the $a_i\ge 1$ positive integers.

Then we probably have that : $\log(n)<\phi((\phi(n))$.

Indeed $\log(n)=a_1\log(p_1)+...+a_k\log(p_k)$ and let's compute $\phi(\phi(n))$.

For $p=2^a$ it's ok.

If all the $p_i\ge 3$ and $a_i\ge 1$ we will have $\phi(\phi(n))=2^k\prod \limits_{i=1}^{k} p_1^{a_i-2}(p_i-1)\phi(M_i)$ where $M_i$ is an odd natural number. If $M_i=q_{i_1}^{b_{i_1}}...q_{i_r}^{b_{i_r}}$ with $3\le q_{i_l} < p_i$ and $b_{i_l}\ge 1$ then $\phi(M_i)=q_{i_1}^{(b_{i_1-1})}(q_{i_1}-1)...q_{i_r}^{(b_{i_r}-1)}(q_{i_r}-1)$ so $\phi(\phi(n))=2^k\prod \limits_{i=1}^{k} p_1^{a_i-2}(p_i-1)q_{i_1}^{(b_{i_1-1})}(q_{i_1}-1)...q_{i_r}^{(b_{i_r}-1)}(q_{i_r}-1)$. I hope that it's $\ge \log(n)$ (could anyone confirm ?)...

Now if $(\mathbb{Z}/\phi(n)\mathbb{Z})^{\times}$ is cyclic and $n$ do not contain $2^1$ in its prime decomposition maybe $\phi(\phi(n))\ge \log(n)$. So there will be at least an element which order is $\phi(\phi(n))$ sand the number of elements of order $\le \log(n)$ will be $\le \phi(\phi(n))$.

We can observe the non-cyclic case. I tried for $(\mathbb{Z}/16\mathbb{Z})^{\times}$ and $(\mathbb{Z}/32\mathbb{Z})^{\times}$ but it's still an inequality. I think it's because of the structure theorem.

Thanks in advance !

• What's the question? – Randall Oct 18 '17 at 17:05
• See first sentence. – Wuestenfux Oct 18 '17 at 18:04
• Why is there a downvote :/ – Maman Mar 29 '18 at 20:08
• It may sound repetitive... but what is the actual question here? Trivially, the number of elements of order bounded by some expression is smaller-or-equal to the total number of elements of the group. Are you wondering if this inequality is always strict (i.e. "Are all elements of $\mathbb{Z}/\varphi(n)\mathbb{Z}$ of order smaller than $\log(n)$?"), or are you looking for some quantitative estimate on the fraction of elements of such order vs. the total number of elements of the group? Or is it something completely different? – Peter Košinár Oct 8 '18 at 20:47
• @PeterKošinár Maybe it is not really precise. I compute several values and find that sometimes (I think it depends on the structure of $(\mathbb{Z}/\phi(n)\mathbb{Z})^*$) we have equality (i.e every elements of this group have an order $\le \log(n)$). But I was wondering if is it possible that for some other values we have $\mid (\mathbb{Z}/\phi(n)\mathbb{Z})^* \mid \ge \text{or} \le \log(n)$ ? And moreover to find conditions on the structure of this group. I hope it's clearer. – Maman Oct 8 '18 at 21:15

We have $\phi(\phi(5)) = \phi(4)=2 > 1.6094... = \log(5)$ but $\phi(\phi(10))=\phi(4)=2 <2.3025...=\log(10)$.
• It seems that for every positive integer $n$ which contains $2^1$ in its prime decomposition we have $\log(n)>\phi(\phi(n))$ – Maman Oct 19 '17 at 20:38