### 255's blog

By 255, history, 7 weeks ago,

Hello Codeforces, recently, there was a contest on CSAcademy named "FiiCode 2021 Round 2" and there was a task "Clown Fiesta", in a editorial for the task, there were lines such like:

If we take a sequence, where $a_0 = m$, $a_1 = \varphi (a_0)$, $a_2 = \varphi (a_1)$, $...$, $a_{k-1} = \varphi (a_{k-2}) \neq 1$, $a_k = \varphi (a_{k-1}) = 1$ and $m$ is prime number less than $10^9$, then $k$ will be not greater than $log_2(m)$.

Can someone prove it?

•  » » 7 weeks ago, # ^ |   +36 This proofs, that $k \leq 2 * log_2(m)$. Actually we can proof, that $k \leq log_2(m) + 1$, because $\varphi(x)$ is even for all $x > 2$. Proof: If $gcd(n, x) = 1$, then $gcd(n, n - x) = 1$ too, and if $n$ is even and $n > 2$, then $gcd(n, \frac{n}{2}) \neq 1$, so all numbers coprime with $n$ are splited in pairs.