How can I formally prove that $3\mid 2^n+1\iff n=2m+1,m \in \mathbb N$

Question

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.

Answer 1

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.

Answer 2

Modulo $3$, $2^n+1=(-1)^n-(-1)$, which is $0$ iff $n$ is odd.

Answer 3

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.

Answer 4

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?

Answer 5

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).$$

Answer 6

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$.