Lower bounding the multiplicative order of 2 modulo p For $p$ prime denote by $\mathsf{ord}_p(2)$ the multiplicative order of $2$ modulo $p$.
Does there exist $N > 0$ such that, for ALL primes $p$, $\mathsf{ord}_p(2)$ is at least $\frac{(p-1)}{N}$?
If there are infinitely many Mersenne primes then the answer is "no".  Since the order of $2$ modulo a Mersenne prime $p=2^k-1$ is only $k$, which is not greater than $\frac pN$  for sufficiently large $p$.
Is there a proof that the answer is "no"?
It is possible that the following question answers this, but it wasn't clear to me:
The critical exponent in the multiplicative order of 2 modulo primes
Thanks
   Steven Galbraith
 A: Here are a few aspects that have not yet been mentioned by
Felipe, Joe and Vesselin.
a) Assuming GRH, 2 is a primitive root mod $p$ for a positive
density of primes. (The density is 0.373955, known as Artin's constant).
For a great survey on this see Pieter Moree,
Integers, Volume 12A (2012), A13: Artin's Primitive Root Conjecture -- A
Survey --
http://www.integers-ejcnt.org/vol12a.html
Moreover, on GRH Hooley proved
that for fixed $L$ there is a
positive density of primes, where the order of 2 mod p, $\text{ord}_p(2)$ is $\frac{p-1}{L}$. ($L$ is also called the index).
Murata worked out that this density roughly decreases as $1/L^2$.
The sum (over $L$) of these densities converges to 1.
For a convenient statement of this see Pappalardi,
On Hooley's Theorem with weights. Rend. Sem. Mat. Polit. Univ. Torino 53 No. 4 (1995) 375-388.
http://www.mat.uniroma3.it/users/pappa/papers/Rend_Sem_Torino_53_1995.pdf
For another statement, assuming GRH, that the average value of the order is quite large, see for example Thm. 2 of Kurlberg and Pomerance:
ON A PROBLEM OF ARNOLD: THE AVERAGE
MULTIPLICATIVE ORDER OF A GIVEN INTEGER
https://math.dartmouth.edu/~carlp/arnoldfinal.pdf
b) Your question whether $\frac{p-1}{\text{ord}_p(2)}$ can actually be
bounded has appeared in the Monthly a while ago:
E3216
Jon Froemke, Jerrold W. Grossman, O. P. Lossers
The American Mathematical Monthly, Vol. 96, No. 4 (Apr., 1989), p. 361.
http://www.jstor.org/stable/2324098?seq=1#page_scan_tab_contents
In short, the published solution gives a proof that it is not bounded, based on
Dirichlet's theorem on primes in progression, and mentions that other
proofs exist that are "not completely elementary",
(e.g. including Chebotarev).
c) Unconditionally, one can show that $\text{ord}_p(2)\geq p^{1/2 + \varepsilon(p)}$, for most primes, where $\varepsilon(p)$ tends to 0, as $p$ tends to infinity. See Erdos and Ram Murty,
On the order of a mod p, CRM Proceedings and Lecture Notes, Volume 19, (1999) pp. 87-97. 
http://www.mast.queensu.ca/~murty/erdos.dvi
Moreover, one can show that for a positive proportion of primes
the order is a bit larger, $> p^{0.677}$, where the exponent comes from a result of Baker and Harman on the largest prime factor of $p-1$. 
See Lemma 20, Kurlberg and Pomerance, On the period of the linear congruential and power generators, P. Kurlberg and C. Pomerance, Acta Arith. 119 (2005), 149–169. 
http://www.math.dartmouth.edu/~carlp/PDF/par13.pdf
In other words, what is known unconditionally is much weaker than what is known on GRH.
A: Fix a prime $q>N$ and find a prime $p$ that splits completely in the splitting field of $x^q-2$. Then $p \equiv 1 \pmod q$ and $2$ is a $q$-th power modulo $p$, so the order of $2$ is at most $(p-1)/q$. Using effective Chebotarev, you can even give an upper bound for the smallest $p$.
Welcome to MO!
A: $\def\ord{\operatorname{ord}}$On the other hand, there are results which say that $\ord_p(2)$ is generally fairly large. For example, an old result of Erdos and Turan says that for any $a\ge2$ and any $\epsilon>0$, the following sum converges:
$$ \sum_{m=1}^\infty \frac{1}{m\cdot \ord_m(a)^\epsilon}. $$
If you're just interested in primes, there's the following more precise result (Murty, Rosen, me)
$$ \sum_{p~\text{prime}} \frac{\log p}{p\cdot\ord_p(a)^\epsilon}
       \le \log\log a + \frac2\epsilon + C
$$ for an absolute constant $C$. 
One can use this to show that the (upper) density of the set $\{p : \ord_p(a)\le p^\theta\}$ is at most $2\theta$. Pomerance has stronger estimates for this density using deeper methods.
Let me second Felipe's welcome to MathOverflow.
A: In the paper 
On the Order of Finitely Generated Subgroups of $\mathbb{Q}^{*}$ (mod $p$) and Divisors of $p-1$,  Journal of Number Theory 57, pp. 207-222
by F. Pappalardi, 
Let $a>1$ non-square. Denote by $l_a(p)$ the multiplicative order of $a$ modulo $p$. Then we have for some positive $\gamma$, 
    $$
    \sum_{p<x} \frac{1}{l_a(p)} \ll \frac{\sqrt{x}}{(\log x)^{1+\gamma}}.$$
It seems that breaking $\sqrt x$ on the upper bound is very difficult. 
If your assertion is true, then the upper bound would have $N \log\log x$ which is way beyond the upper bound $\sqrt x / (\log x)^{1+\gamma}$. 
