# 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).

-
Well, the question comes from something I was reading and perhaps I misinterpreted the statement. Does "a prime number with order base 2 less than or equal to x" mean the multiplicative order of 2 mod p, such that k is greater than x? –  Dorse Oct 29 '11 at 14:24
Sorry, I meant such that k is less than or equal to x. –  Dorse Oct 29 '11 at 14:39

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
So it's impossible to figure it out just based on what b is and nothing else? –  Dorse Oct 29 '11 at 3:29