Multiplicative order of 2 mod p

Question

I'm looking for a formula that produces the multiplicative order of 2 mod p, or any insight that makes calculating it better than guessing and checking. Here's what I've come up with

By Fermat's Little Theorem,

$$2^{p-1} \text{ mod } p \equiv 1$$ This means that the order must divide $p-1$ evenly. At first, I thought that the order must always be $p-1$ but I can come up with counterexamples, such as

$$2^{11} \text{ mod } 23 \equiv 1$$ This makes me think that for every number of the form $2^p-1$ which isn't a prime, $p$ becomes the smallest order for 2 mod a factor of $2^p-1$. In this case, note that

$$2^{11}-1 = 23*89$$

After this I get stuck, so my question is as follows: Is there a formula that produces the multiplicative order of 2 mod p for any p? Maybe a formula is too greedy since having a formula would allow us to check if any number of the form $2^p-1$ was prime simply by seeing if $p$ was the order of 2 mod p for any prime p, but is there a pattern or something to the distribution of the orders that is worth noticing or mentioning? Or is there further reading on this topic that I could look into? Any OEIS links or relations to the Riemann zeta function I haven't noticed? Any help would be appreciated, thanks!

Answer 1

Concerning how to determine the multiplicative order, one of the few algebraic tools is the aspect, that

• if $p$ is a prime, then the order $\lambda_{2,p}$ is not completely arbitrary but a divisor of $p-1$, so $\lambda_{2,p} \mid p-1$ and moreover $p \mid 2^{\lambda_{2,p}}-1$ (and not only $p \mid 2^{p-1}-1$).
• Plus it cannot of course be smaller than $\log_2(1+p)$ , so for $p=127$ we have $\lambda_{2,127} \ge 7$ although as well $2$ is a divisor of $p-1=126$.

So you have to check only the divisors of $p-1$ : test $\lambda=p-1$,$\lambda=\frac{p-1}2$ ,$\lambda=\frac{p-1}{d_k}$ ,... downwards while $p|2^\lambda-1$ and $\lambda \ge \log_2(1+p)$.

Disclaimer: this is only the most basic knowledge; there are more properties of $p$ resp. $p-1$ which can shorten that search but I don't have it at hand.

It is also worth to note, that $2^{\lambda}-1$ is possibly not only divisible by $p$ but also by a power of $p$, so we might write $p^{\alpha_{2,p}} | 2^{\lambda_{2,p}}-1$ and have $\alpha_{2,p}>1$ as for the Wieferich-primes $1093$ and $3511$ where $\alpha_{2,p}=2$ . Only this two ones are known, and it is so far unknown whether there exist more at all. If you take another base, say $b=3$ and ask the same thing for $p=11$ then you find $\lambda_{3,11}=5$ and $\alpha_{3,11}=2$, so $11^2 | 3^5 -1$.

Due to Euler we know moreover, that after $p^{\alpha_{b,p}} | b^{\lambda_{b,p}}-1$ then $p^{\alpha_{b,p}+k} | b^{\lambda_{b,p} \cdot p^k}-1$ . A proof that the value $k$ on each exponent is indeed equal on both sides of the divisibly-statement is usually not provided together with this rule, but it can be done with elementary means; one proof can be found when searching for "LTE-lemma" or "Lifting-the-exponent-lemma". But as well in the essay that I linked to in my first comment, I propose a little algebra of the $\lambda$ and $\alpha$ and give a proof for this specific property.

Finally, if you have a composite $n=pq$ with the two (or of course more) primes then you can compute $\lambda_{2,n} = \text{LCM}(\lambda_{2,p},\lambda_{2,q})$ and apply all properties as mentioned above adequately. So for instance, if $n=pq=3\cdot 7=21$ then $n | 2^m-1$ when $m=\text{LCM}(2,3)=6$ and $2^6-1=63$ is divisible by $21$.