Could I apply the master theorem if my $N/b$ is $\varphi(N)$?
You can not apply the master theorem directly. However, you can play with your expression a bit to get an upper bound on which you can then apply the master theorem.

First, show that $\phi(\phi(n)) &lt; n/2$. This can be done as such:

Let $n = \prod_{i=1}^rp_i^{k_i}$ be the prime factorisation of $n$ ($p_i$ prime, $k_i&gt;0$)


Suppose $n$ is even. Then $\phi(n) = n\prod_{i=1}^r(1-\frac{1}{p_i}) \leq n(1-\frac{1}{2}) \leq n/2.$ Thus $\phi(\phi(n)) &lt; n/2$.
Suppose $n$ is odd and $n &gt; 1$. Then $\phi(n) = \prod_{i=1}^r (p_i-1)p_i^{k_i-1}$ is even and smaller than $n$. By the previous result $\phi(\phi(n)) &lt; n/2$.


So we get the desired result.

Now suppose $n\geq2$. You can write:
$$T(n) = T(\phi(n))+\log(\phi(n))^3 = T(\phi(\phi(n)))+\log(\phi(\phi(n)))^3 + \log(\phi(n))^3.$$
$$T(n) \leq T(n/2) + 2\log(n)^3.$$

Now you can apply the master theorem here to get:
$$T(n) = O(log(n)^4).$$