Multiplicative order of $2$ modulo $p$.

Question

When calculating the multiplicative order of $2$ modulo a prime $p$ you often get $p-1$ or $\frac{p-1}{2}$ as a result, but there are cases where this does not hold, is there a general form for those primes for which this does not hold?. For example, the order of $2$ modulo $89$ is $11$, why is that so?

Answer 1

Using the first $5000$ or so primes, we find that the multiplicative order of smaller primes mod $p$ is distributed very similarly for all the primes, not just $2$. On average, a given prime has a multiplicative order of $(p-1)/k$ with approximately proportion $p$:

$$ \begin{array}{c c} k=1 & p \approx 37 \% \\ k=2 & p \approx 27 \% \\ k=3 & p \approx 7 \% \\ k=4 & p \approx 7 \% \\ \end{array} $$

and then generally decreasing.

Surprising result: the value of $k$ for $5$ is never an odd multiple of $5$, no matter the modulus.