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
    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?2011-10-29
  • 0
    Sorry, I meant such 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
    I am not sure I understand the question. But certainly $b$ can have order $>1$ and $$p$. – 2011-10-29
  • 0
    So it's impossible to figure it out just based on what b is and nothing else?2011-10-29