# 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?

• The Maple code $2^{222}-1 \mod 3$ outputs $0$. – user64494 Mar 12 '15 at 20:01

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

• Thank you a lot for the link. Actually you help me very much. Thanks!! – Klochkovskiy Mar 12 '15 at 14:09

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.

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

• thanks to you, now I've just discovered it for myself – Klochkovskiy Mar 12 '15 at 14:19
• You know... I read about binomial theorem, but actually it looks like not the same as your... it's not like what you wrote here. What is M? Can you give me a useful link with explanation or something like of if you don't mind? – Klochkovskiy Mar 12 '15 at 16:06
• Ahh okay good, here $M$ is some integer. Expand $(3-1)^{222}$ using binomial theorem and soon you will notice that all the terms are multiples of $3$ except the last term which would be $1$. $$\color{blue}{(3-1)^{222} = \binom{222}{0}3^{222} - \binom{222}{1}3^{221} + \cdots + \binom{222}{220}3^2 -\binom{222}{221}3^1 + \binom{222}{222}3^0 = 3M + 1}$$ – AgentS Mar 12 '15 at 16:21
• You might find below results based on binomial thm interesting $$(x+1)^n = Mx + 1\\ (x-1)^n = Mx + (-1)^n\\(x+a)^n = Mx + a^n$$ – AgentS Mar 12 '15 at 16:28
• Alternatively (this is really the same proof but hiding the binomial stuff), since $2\equiv-1$ also $2^{222}\equiv(-1)^{222}=1$. – Mario Carneiro Mar 13 '15 at 3:27

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

• I'm thankful for your one. Thanks, it's seemed to be the most readable and understandable for me and for anyone else – Klochkovskiy Mar 12 '15 at 14:17

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

• This all is seemed to be number theory... I don't really know it well I've never faced it directly. But your explanation is very interesting, so thank you a lot for this – Klochkovskiy Mar 12 '15 at 14:12

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

• I'm a bit confused seeing this. But I'm grateful for your explanation – Klochkovskiy Mar 12 '15 at 14:15
• @Klochkovskiy Let me know what proves confusing so I can elaborate. – Bill Dubuque Mar 12 '15 at 14:29

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.