$\gcd\left(\dfrac{m}{\gcd(m,a ^ i)}, a\right) = 1$ となる最小の非負整数 $i$ を $i _ 0$ とおく。また、$m _ 0 = \dfrac{m}{\gcd(m, a ^ {i _ 0})}$ とおく。
$m \geq 2 \Rightarrow \varphi(\varphi(m)) \leq \dfrac{1}{2}m$ および $d \mid m \Rightarrow \varphi(d) \mid \varphi(m)$ より、2 回再帰するたびに $m$ は半分以下になるので、再帰の深さは $O(\log m)$ である。