12
$\begingroup$

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?

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

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you a lot for the link. Actually you help me very much. Thanks!! $\endgroup$ – Klochkovskiy Mar 12 '15 at 14:09
54
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
26
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thanks to you, now I've just discovered it for myself $\endgroup$ – Klochkovskiy Mar 12 '15 at 14:19
  • $\begingroup$ 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? $\endgroup$ – Klochkovskiy Mar 12 '15 at 16:06
  • 1
    $\begingroup$ 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}$$ $\endgroup$ – AgentS Mar 12 '15 at 16:21
  • $\begingroup$ 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$$ $\endgroup$ – AgentS Mar 12 '15 at 16:28
  • 1
    $\begingroup$ Alternatively (this is really the same proof but hiding the binomial stuff), since $2\equiv-1$ also $2^{222}\equiv(-1)^{222}=1$. $\endgroup$ – Mario Carneiro Mar 13 '15 at 3:27
10
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm thankful for your one. Thanks, it's seemed to be the most readable and understandable for me and for anyone else $\endgroup$ – Klochkovskiy Mar 12 '15 at 14:17
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Klochkovskiy Mar 12 '15 at 14:12
3
$\begingroup$

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

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

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.