<s>[INST] 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.
 [/INST] 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?
</s>