Proof that $2^{222}-1$ is divisible by 3

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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.

Answer 6

${\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$

Answer 7

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.