How can I formally prove that $3\mid 2^n+1\iff n=2m+1,m \in \mathbb N$ How can I formally prove that two to the power of some n all plus one is divisible by three when n is odd (1,3,5,7,...)? Or, another words,$$2^n+1=3k \Leftrightarrow (n=2m+1,m \in \mathbb N)\bigwedge(k \ge 1,k \in \mathbb N)$$It is actually true, for example:$$2^1+1=2+1=3=3\cdot1\\2^3+1=8+1=9=3\cdot3\\2^5+1=32+1=33=3\cdot11\\etc.$$
The Little Fermat's theorem does NOT look quite convenient for this case. Should I consider the group $1+\mathbb Z/3\mathbb Z$? Considering $2^{2\cdot m+1}+1=2\cdot2^{2m}+1=2\cdot4^m+1=3\cdot(???)?$  It just has no sense.
 A: If you know modular arithmetic this is simple:
$$2^n+1 \equiv (-1)^n+1 \pmod{3}$$
Your question then becomes Prove that $(-1)^n+1 \equiv 0 \pmod{3}$ if and only if $n$ is odd.
A: Modulo $3$, $2^n+1=(-1)^n-(-1)$, which is $0$ iff $n$ is odd.
A: Note that $$2^n+1 \equiv (-1)^n+1 (mod 3)$$
 For odd values of $n$ we have $$(-1)^n+1\equiv 0 (mod 3)$$
For even values of $n$ we have $$ (-1)^n+1 \equiv 2 (mod 3)$$ 
Thus $2^n +1 $ divides $3$ if and only if $n$ is odd. 
A: 1) Let $n$ be odd.
Polynomial.$y:= x^n+1^n$, has a zero at $x=-1$.
$(x-(-1)) =(x+1)$ is a factor.
$x^n+1^n= (x+1)p_{n-1}(x)$, where $p_{n-1}$ is a polynomial of degree   $n-1$.
$x=2$: 
$2^n +1= (2+1)p_{n-1}(2)$, and we are done.
2) Le n be even.
$y= x^n+1^n$; 
Is $x=-1$ a zero, i.e $(x+1)$ a factor?
A: Here's an explicit calculation and demonstration, not reducing modulo $3$.    
If $n=2m+1$, then
$$2^n+1=2+2^n-1=2+\sum_{k=0}^{n-1}2^k=2+1+\sum_{k=1}^{n-1}2^k$$
$$=2+1+\sum_{j=1}^{m}(2^{2j-1}+2^{2j})=3+\sum_{j=1}^m(1+2)2^{2j-1}=3\left(1+\sum_{j=1}^m2^{2j-1}\right).$$
A: It can be viewed as a special case of a handy basic consequence of the $\rm\color{#c00}{order}$ of an element.
$\!\bmod 3\!:\,\ 0\,\equiv\, 2^{ N}\!+1\,\equiv\, (-1)^{N}+1\!\iff\! (-1)^{\color{#0a0}N}\equiv\, (-1)^{\large\color{#0a0}1}\!\!\iff \color{#0a0}{N\equiv\, 1}\pmod{\!\color{#c00}2},\ $ by
modular exponent reduction $ $ if $\,a\,$ has $\,\color{}{{\rm order}\,\ \color{#c00}\ell}\ $ then  $\ a^{ \color{#0a0}N}\! \equiv a^{\color{#0a0}K}\!\!\iff\! \color{#0a0}{N\equiv K}\pmod{\!\color{#c00}\ell}$
using the simple observation: $\ {-}1\,$ has order $\,\color{#c00}2\,$ by $\ (-1)^{\large 1}\!\not\equiv 1,\,\ (-1)^{\large\color{#c00}2}\equiv 1$.
