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 !

  • $\begingroup$ What's the question? $\endgroup$ – Randall Oct 18 '17 at 17:05
  • 1
    $\begingroup$ See first sentence. $\endgroup$ – Wuestenfux Oct 18 '17 at 18:04
  • $\begingroup$ Why is there a downvote :/ $\endgroup$ – Maman Mar 29 '18 at 20:08
  • $\begingroup$ 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? $\endgroup$ – Peter Košinár Oct 8 '18 at 20:47
  • $\begingroup$ @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. $\endgroup$ – 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)$.

  • $\begingroup$ So maybe if the group is cyclic we can have equality $\endgroup$ – Maman Oct 19 '17 at 16:02
  • $\begingroup$ It seems that for every positive integer $n$ which contains $2^1$ in its prime decomposition we have $\log(n)>\phi(\phi(n))$ $\endgroup$ – Maman Oct 19 '17 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.