# Multiplicative order bounds

For the equation $b^k\equiv 1 \pmod p$, where $p$ is prime, how do I find a lower bound for $p$ such that $k$ will never be smaller than a given number, no matter how large $p$ gets?

-

If $b$ is fixed and greater than 1, then $b^k\equiv1\pmod p$ implies $b^k\ge1+p$, so $k$ must be at least $\log(p+1)/\log b$. This is best possible in the (rather weak) sense that if $b$ is 2 we could have $b^k=1+p$. But maybe I've misunderstood the problem (in which case I hope OP will clarify).
Unless $b \equiv 1$, we will always have $k = np-1$ for some natural $n$. So $k$ will never be smaller than $p-1$
I am not sure I understand the question. But certainly $b$ can have order $>1$ and $<p-1$ modulo $p$. –  André Nicolas Oct 29 '11 at 2:56