0
$\begingroup$

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?

2 Answers 2

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

  • 0
    Sorry, 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$

  • 0
    So it's impossible to figure it out just based on what$b$is and nothing else?2011-10-29