Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

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

share|improve this answer
    
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$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.