0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.