Efficient upper bound on potential $k$'s for $q \mid b^k$

Question

I am trying to write an algorithm that will, given $b, q \in \mathbb{Z}$, determine:

whether or not all prime factors of $q$ are also factors of $b$

I learnt here that this was equivalent to trying to find if:

$\exists \; k \in \mathbb{Z}$ such that $q \mid b^k$

Now I just need to skim through the potential $k$'s, find $b^k$ and see if $q \mid b^k$. But I have a problem. I can't figure out an efficient upper bound on potential $k$'s. Can somebody help?

Answer 1

The largest exponent occuring in the prime factorization of $q$ is an upper bound for $k$. A bound that always works is $$\lceil \log_2(q) \rceil$$