Integer $m$ such that $2^m\equiv\pm 1\pmod{2n+1}$ Let $n$ be a positive integer. Does there always exist a positive integer $m\leq n$ such that $2^m\equiv\pm 1\pmod{2n+1}$?
It is true that $2^{\phi({2n+1})}\equiv 1\pmod{2n+1}$. If $2n+1$ is prime, the statement follows by taking $m=\phi(2n+1)/2$. But if $2n+1$ is composite, then it might be possible that $2^{\phi({2n+1})/2}$ is not $\pm 1\pmod{2n+1}$.

Suppose that there exist positive integers $m_1<m_2\le n$ such that $2^{m_1}\equiv 2^{m_2}(\operatorname{mod} 2n+1)$. Then $2^{m_2-m_1}(2^{m_1}-1)$ is divisible by $2n+1$. Since $\operatorname{GCD}(2^{m_2-m_1},2n+1)=1$, we see that $2^{m_1}-1$ is divisible by $2n+1$. Now consider numbers $2^0,2^2,\dots, 2^n$. If $2^{m}\equiv 1 (\operatorname{mod} 2n+1)$ then the claim is proved. So assume the converse. Then residues $2^0,2^2,\dots, 2^n$ are mutually different modulo $2n+1$. Then residues $-2^0,-2^2,\dots, -2^n$ are mutually different modulo $2n+1$ too. Since each of these two set of residues contains $n+1$ element,  and $2(n+1)>2n+1,$ by pigeonhole principle, there exist integers $0\le m_1<m_2\le n$ such  that $-2^{m_1}\equiv 2^{m_2}(\operatorname{mod} 2n+1)$. Then $2^{m_2-m_1}(2^{m_1}+1)$ is divisible by $2n+1$. Since $\operatorname{GCD}(2^{m_2-m_1},2n+1)=1$, we see that $2^{m_1}+1$ is divisible by $2n+1$. 
