Prove that if $\operatorname{ord}_{2m+1}(2) > m$, then $2$ is a generator of the invertible elements modulo $2m+1$ 
Let $m$ be a positive integer. Prove that if $\operatorname{ord}_{2m+1}(2) > m$, then $2$ is a generator of the invertible elements modulo $2m+1$.

We need to prove that if $\operatorname{ord}_{2m+1}(2) > m$, then $\operatorname{ord}_{2m+1}(2) = \varphi(2m+1)$. For example, if $m = 4$ then $2m+1 = 9$ and $\operatorname{ord}_{9}(2) = 6 > 4$ and $\operatorname{ord}_{9}(2) = \varphi(9)$. How do we prove the result in general?
 A: It's an application of Lagrange's theorem (also stated here) that $$ord_{n}(a) \mid \varphi(n)$$
and
$$m<ord_{2m+1}(2)\leq\varphi(2m+1)<2m+1$$
or 
$$m<ord_{2m+1}(2)\leq\varphi(2m+1)\leq2m$$
So, if $\varphi(2m+1)=k\cdot ord_{2m+1}(2)$ and we assume $k\geq2$ then $\varphi(2m+1)>2m$, which is a contradiction, so $k=1$.
A: Hint $\ 2$ has order $\,n\mid \phi \le 2m.\,$ As in the Order Test below, if  $\,n < \phi$ then it arises by deleting at least one prime factor $p$ from $\phi,\,$ so $\,n\le \phi/p \le \phi/2\le m,\,$ contra hypothesis. Hence $\,n = \phi.$

Order Test $\,\ \,a\,$ has order $\,n\iff a^{ n} = 1\,$ but $\,a^{n/p} \not= 1\,$ for every prime $\,p\mid n.\,$ 
Proof $\ (\Leftarrow)\ $ If $\,a\,$ has $\,\rm\color{#c00}{order\ k}\,$ then $\,k\mid n.\,$  If $\,k < n\,$ then $\,k\,$ is proper divisor of $\,n\,$ therefore $\,k\,$ must omit at least one prime $\,p\,$ from the unique prime factorization of $\,n,\,$ hence $\,k\mid n/p,\,$ say $\, kj = n/p,\,$ so $\,a^{n/p} = (\color{#c00}{a^k})^j= \color{#c00}1^j= 1,\,$ contra hypothesis. $\ (\Rightarrow)\ $ By definition of order.
