Prime numbers which solve $2^s=1\pmod p$

Here we define those primes $p$ for which $\operatorname{ord}_p(2)=s$, where $s$ is the minimum of the set $S$ of all divisors $d\mid p-1$ such that $2^d-1\geq p$.

For example: for $p=7$, $s=3$, $7\mid 2^3-1$ thus $\operatorname{ord}_p(2)=s=3$ ($7$ is such a prime).

Questions: how many such primes are there? Are such primes interesting?

Thanks.

-

migrated from meta.math.stackexchange.comApr 17 '11 at 1:26

This question came from our discussion, support, and feature requests site for people studying math at any level and professionals in related fields.

JFYI: I've opened a bug report about tomerg losing ownership to this question after the migration. This is somewhat unexpected. – Willie Wong Apr 17 '11 at 2:38

If $p$ is a prime, one less than a multiple of $8$, and one more than twice a prime, then it satisfies the condition. This explains $7$; the next such example is $23$. It is generally believed, but not proved, that there are infinitely many primes satisfying the conditions I have given.

There are primes that satisfy your condition but not mine, e.g., $17$.

"Interesting" is a subjective term. I found them interesting enough to spend a few minutes writing up this answer.

EDIT: It seems I can't comment on tomerg's answer, so I'll put my comment here.

@tomerg, yes, I said there are primes of your kind that are not of my kind, and I gave $17$ as an example. $73$ is also an example. You wanted to know how many of your primes there are, and I have given a good reason to believe (but not a proof) that there are infinitely many. I hope someone else can build on what I've done, and give a complete answer. But this may be difficult, so I've done what I can.

-
I don't know how to write a comment to you Gerry Myerson, so I write an answer. Your condition seems to be interesting but there are some counter-examples for prime of the kind I gave which are not of your kind. For example: 73. – tomerg Apr 17 '11 at 11:33
@tomerg: I manually moved your comment. I apologise for the inconvenience, your original posting of the question to Meta instead of the main site seems to have triggered a bug, which made you unable to comment on your own question. (See my comment to your question.) I hope this would be resolved soon (but it is out of the hands of the moderators). – Willie Wong Apr 17 '11 at 12:22
@tomerg: for the time being, please add all comments you have on this question as answers, and "flag" them for moderator attention with where the comment should go. (@Gerry, sorry about the Pings) – Willie Wong Apr 17 '11 at 12:25
Now that I think about it, $73$ isn't an example, is it? Don't we get $s=9$, but $8$ is a divisor of $p-1$, and $2^8-1\ge73$? – Gerry Myerson Apr 18 '11 at 0:32