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

176 Views Asked by At

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 !

1

There are 1 best solutions below

2
On

We have $\phi(\phi(5)) = \phi(4)=2 > 1.6094... = \log(5)$ but $\phi(\phi(10))=\phi(4)=2 <2.3025...=\log(10)$.