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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ The Maple code $2^{222}-1 \mod 3$ outputs $0$. $\endgroup$– user64494Commented Mar 12, 2015 at 20:01
Add a comment
|
7 Answers
$\begingroup$
$\endgroup$
0
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.
$\begingroup$
$\endgroup$
6
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}$$
-
$\begingroup$ thanks to you, now I've just discovered it for myself $\endgroup$ Commented Mar 12, 2015 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$ Commented Mar 12, 2015 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$– AgentSCommented Mar 12, 2015 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$– AgentSCommented Mar 12, 2015 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$ Commented Mar 13, 2015 at 3:27
$\begingroup$
$\endgroup$
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$.
-
$\begingroup$ Thank you a lot for the link. Actually you help me very much. Thanks!! $\endgroup$ Commented Mar 12, 2015 at 14:09
$\begingroup$
$\endgroup$
1
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
-
$\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$ Commented Mar 12, 2015 at 14:17
$\begingroup$
$\endgroup$
1
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)$$
-
$\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$ Commented Mar 12, 2015 at 14:12
$\begingroup$
$\endgroup$
2
${\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$
answered Mar 12, 2015 at 13:51
-
$\begingroup$ I'm a bit confused seeing this. But I'm grateful for your explanation $\endgroup$ Commented Mar 12, 2015 at 14:15
-
$\begingroup$ @Klochkovskiy Let me know what proves confusing so I can elaborate. $\endgroup$ Commented Mar 12, 2015 at 14:29
$\begingroup$
$\endgroup$
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.
answered Mar 13, 2015 at 23:26