Divisibility of $2^n+1$ Is there a way to prove that no number of the form $2^n+1$ is divisible by $7$ or $23 \,$? I just stumbled over this and am wondering if the pattern holds and why.
Edit: Thanks guys, I also found $A072936$
 A: By Fermat's little theorem, $2^6\equiv1\pmod7$, so the powers of $2$ modulo $7$ are periodic with period $6$.  If none of $2^1,2^2,\dots,2^6$ is congruent to $-1\pmod7$, then you're done.  Since $23$ is also prime, checking $22$ consecutive powers of $2$ modulo $23$ will dispose of that case.
In this particular case, you can be more efficient.  If $2^n\equiv-1\pmod p$ then $2^{2n}\equiv1\pmod p$ and then we must have $2n|p-1$.  So when $p=23$, for example, we must have $2n|22\implies n|11$ and the only choices are $n=1$ and $n=11$.  We know $n=1$ doesn't work, so we only have to check $2^{11}$.
Also, we may be able to use some failures to preclude other possibilities.  Take $p=79.$ $2n|78\implies n|39$ which gives the possibilities $n=1,3,13,39$.  We find $2^{39}\equiv1\pmod{79}$  Now we don't have to bother checking $2^{13}$.  If $2^{13}\equiv-1\pmod{39}$ then cubing both sides gives $2^{39}\equiv-1\pmod{79}$ which we know to be false.  Similarly, we don't have to check $2^3$.
A: $$2^n\equiv-1\pmod{23}\implies 2^{2n}\equiv1$$
But $2^{22}\equiv1\pmod{23}$
$\implies2^{(2n,22)}\equiv1$
Now $(2n,22)=2(n,11)=\begin{cases}2 &\mbox{if } 11\nmid n\\22 & \mbox{if } 11\mid n \end{cases}$
But $2^2\not\equiv-1\pmod{23}$
Now $2^{22}-1=(2^{11}-1)(2^{11}+1),$ we need $2^{11}\equiv-1$
But $2^5\equiv9\pmod{23}\implies2^{11}\equiv2\cdot9^2\equiv2\cdot12\equiv1\not\equiv-1\pmod{23}$
A: Note  for $\,p=7,23\,$ we have $\!\bmod p\!:\ \color{#0a0}{2^m\equiv 1},\, m = (p\!-\!1)/2,\,$ by $\,2\equiv 3^2,5^2$ resp. is a square. Furthermore $\,m\,$ is odd $ $ hence $\,(\color{#0a0}{2^m-1},2^n+1)=1$ so $\,p\mid \color{#0a0}{2^m-1}\Rightarrow \,p\nmid {2^n+1}.\,$ QED
Remark $ $ The linked proof shows it is a special case of the following order-theoretic coprimality inference (and explains how it is an analog of a well known property of fraction denominators).
Lemma $\,\ $ If $\ (\color{#0a0}m,\color{#c00}k)=1\,$ then $\, a^{\large\color{#0a0}m}\equiv 1\equiv a^{\large\color{#c00}{k}\:\!n}\, $ $\Rightarrow\, a^{\large n}\equiv 1$
Proof $\ $ By here $ \ {\rm ord}\ a\mid m,kn\, \Rightarrow\, {\rm ord}\ a\mid \underbrace{(\color{#0a0}m,\color{#c00}k\:\!n)\!=\!(m,n)}_{\large (\color{#0a0}m,\,\color{#c00}k)\,=\,1\qquad\!}\mid n\,\Rightarrow\, a^{\large n}\equiv 1$
A: mod $7$:
$2^n \equiv -1
\implies 2^{2n} \equiv 1
\implies $ $3$ divides $2n$
$\implies$ $3$ divides $n$
$\implies$ $2^n \equiv 1$, contradiction
mod $23$:
$2^n \equiv -1
\implies 2^{2n} \equiv 1
\implies $ $11$ divides $2n$
$\implies$ $11$ divides $n$
$\implies$ $2^n \equiv 1$, contradiction
The main point here is that if the order of $2$ mod $p$ is odd, then $p$ cannot divide $2^n+1$. Or equivalently, if $p$ divides $2^n+1$ for some $n$, then the order of $2$ mod $p$ is even.
