You can do b = b % phi(mod)

(euler totient function)

Well, first of all, for your example you can always just do fast exponentiation, in O(log b) multiplications. If b is even, then a^b = (a^b / 2)², otherwise a^b = a^b - 1·a. Though I never implement it recursively, but iteratively (C++):

int pot(int a, int b){
  int r = 1;
  while (b){
    if (b%2) r = mul(r, a);
    a = mul(a, a);
    b /= 2;
  }
  return r;
}

The modding is covered in the mul function.

But to answer your question, yes you can reduce b. If b is greater than φ(mod), then you can reduce b to b%φ(mod) + φ(mod). If you knew that a is relatively prime to mod then you wouldn't need the  + φ(mod), but in the general case it wouldn't work without  + φ(mod) (for example, a = 2, mod = 2²⁰, b = φ(mod) = 2¹⁹, the solution is 0). φ(x) is the Euler totient function.