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

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?

## 1 Answer

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$$

• Yeah, that worked. Thnx. Btw, Is it possible to do even better? – Truth-seek May 16 '18 at 12:35
• In general, no. – Peter May 16 '18 at 13:46