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?
Multiplicative order bounds
0
$\begingroup$
number-theory
modular-arithmetic
2 Answers
2
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).
-
0Sorry, I meant s$u$ch that k is less than or equal to x. – 2011-10-29
0
Unless $b \equiv 1$, we will always have $k = np-1$ for some natural $n$. So $k$ will never be smaller than $p-1$
-
0So it's impossible to figure it out just based on what$b$is and nothing else? – 2011-10-29