Proof that $2^{222}-1$ is divisible by 3 How can I prove that $2^{222}-1$ is divisible by three? 
I already have decomposed the following one: $(2^{111}-1)(2^{111}+1)$ and I understand I should just prove that $(2^{111}-1)$ is divisible by three or that $(2^{111}+1)$ is divisible by three. But how can I solve this problem?
 A: The three numbers $2^{111}-1$, $2^{111}$ and $2^{111}+1$ are consecutive, and so one of them is divisible by $3$. But $2^{111}$ is not, since $2$ is prime.
A: You can use coungrence 
$$2 \equiv 2 \;(\bmod\; 3)$$
$$2^2 \equiv 4 \equiv 1 \;(\bmod\; 3)$$
$$2^3 \equiv 8 \equiv 2 \;(\bmod\; 3)$$
It is easy to conclude (and prove) that:
$$2^{2k} \equiv 1 (\bmod\; 3)$$
$$2^{2k+1} \equiv 2 \;(\bmod\; 3)$$
So $$2^{222} \equiv 1  \;(\bmod\;3)$$
and 
$$2^{222} - 1\equiv 1 - 1 \equiv 0  \;(\bmod\;3)$$
A: ${\rm mod}\,\ 3\!:\ \color{#c00}{2^2\equiv 1}\,\Rightarrow\,2^{J+2K}\equiv 2^J\color{#3c00}{(\color{#c00}{2^2})}^K\equiv 2^J\color{#c00}{1}^K\equiv 2^J.\,$ Yours is $\,J=0,\,K=111$
Remark $\ $ Generally $\ \color{}{a\equiv -1}\Rightarrow\, a^{J+2K}\equiv a^J\,$ by $\,(-1)^{2K}\equiv 1,\,$ as above
Above we used standard Congruence Arithmetic Rules (Product and Power Rules).
This exploitation of periodicity of powers generalizes from squares to any power, namely
Key Idea $ $ Generally, if $\,a^e\equiv 1\pmod m\,$ then exponents on $\,a\,$ can be taken mod $\,e,\,$ i.e. $\ a^{\large j}\equiv a^{\large k}\pmod m\,\ $ if $\,\ j\equiv k\pmod e.\ $ This may be proved exactly as above, i.e.
$$ \begin{array}{}\color{#c00}{a^{\large e}\equiv 1}\\ j = k\! +\! en\end{array}\Rightarrow\,\ a^{\large j}\equiv a^{\large  k+en}\equiv a^{\large  k}\color{#c00}{(a^{\large  e})}^{\large  n}\equiv a^{\large  k}\color{#c00}{(1)}^{\large  n}\equiv a^k\!\!\pmod m\qquad $$
So, in your case $\ {\rm mod}\ 3\!:\,\ 2^{\large \color{#b0f}2}\equiv 1\,\Rightarrow\, 2^{\large 2N}\equiv 2^{\large 2N\ {\rm mod}\, \color{#b0f}2}\equiv 2^0\equiv 1$
A: HINT
If you're familiar with binomial theorem $$\color{blue}{2^{222}}-1 = \color{blue}{(3-1)^{222}}-1 = \color{blue}{1+3M} -1 = \color{blue}{3M}$$
A: The routine way is to invoke Fermat's little theorem: $$a^{p-1}-1\equiv 0\,(\text{mod}\,p)$$ for $\mathrm{gcd}(a,p)=1$.
Plug in $a=2^{111},p=3$.
A: When $n$ is odd we have that $$a^n+1=(a+1)(a^{n-1}-a^{n-2}+a^{n-3}-\cdots-a+1)$$
Plugging in $a=2$ you see that the expression is divisible by 3
A: The simplest way is to compute the powers of 2 modulo 3: 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, ...
Clearly $2^n \equiv 2 \bmod 3$ if $n$ is odd and $2^n \equiv 1 \bmod 3$ if $n$ is even.
So, if $n$ is even ($n = 222$ certainly qualifies), then $2^n - 1 \equiv 0 \bmod 3$ as asserted.
