public static int phi(int num) {
        if (num == 1)
            return 1;
        
        if (isPrime(num))
            return num-1;
        
        if (num % 2 == 0) { //using 2 identity
            num /= 2;
            return (num % 2 == 0 ? 2 : 1) * phi(num);
        }
        
        //this is the identity: phi(m * n) = phi(m) * phi(n) * gcd(m, n) / phi(gcd(m, n)).
        
        int m = findMeADivisor(num), n = num / m;
        int g = gcd(m, n);
        
        return phi(m) * phi(n) * g / phi(g);
    }