I would like to show Pillai's lower bound. Here we use $ \varphi^*(n) $ to denote $ \Phi(n) $ because of the famous log-star function ($ \log^* $) in complexity.
To get started, we need a special variety of Euler's totient function $ \hat\varphi $, which is $\varphi$ without considering 2, namely $ \hat \varphi(x):=\begin{cases}\varphi(x), x\text{ odd}\\ 2\cdot\varphi(x), x\text{ even}\end{cases} $.
When $ k $ goes sufficiently large(actually it is just $ \varphi^*(x) $), it is easy to see that $ \varphi^k $ approaches $1$ and $ \hat\varphi^k $ approaches some power of $ 2$. Let's denote it as $2^{\sigma(x)} \le2^k=2^{\varphi^*(x)} $. The inequility is obvious. Then we make a claim.
Claim. For all odd number $ x $, there holds $ x\le 3^{\sigma(x)} $. The equality holds iff $ x $ is some power of $3$.
Proof of the claim. Obviously $ \sigma(2)=\sigma(3)=1, \sigma(3^k)=k $. And it is also easy to check that $ \sigma(pq)=\sigma(p)+\sigma(q) $. So we just need to deal with the prime numbers. By induction, we consider the prime $ p>3 $. We have known that $ p-1\le 3^{\sigma(p-1)}=:t $, and the equality never holds, so $ p-1<t $. Since $ \sigma(p-1)=\sigma(p) $ for prime $p$, and notice that $ p\neq 3^{\sigma(p)}=t $, from $ p-1<t,p\neq t $, we get $ p<t $.
Eventually the final step.
When $x $ is odd, $ \varphi^*(x)\ge\sigma(x)+1\ge\log_3n+1 $.
When $ x $ is even, we write $ x=2^d\cdot c, d\ge1, c\text{ odd} $, then $ \varphi^*(x)\ge \sigma(x)=d+\sigma(c)\ge d+\log_3c\ge1+ \log_3{x\over2}$. Easy to check the equality holds iff $ x =2\cdot3^k $ for some $ k $.
Here the proof ends.
The proof comes from a proof sketch by Deng Mingyang(moorhsum), the IMO 2019 gold medal winner from China, posted on Zhihu(Chinese), a chinese version of Quora. I prove the claim here which the sketch not contains. I am curious about why to construct such $ \hat\varphi $ and make such a claim.
