37
$\begingroup$

For example \begin{align} 2^5 + 1 &= 33\\ 2^{11} + 1 &= 2049\ \text{(dividing by $3$ gives $683$)} \end{align}

I know that $2^{61}- 1$ is a prime number, but how do I prove that $2^{61}+1$ is a multiple of three?

$\endgroup$
  • $\begingroup$ @AnuragA $2^{61}- 1$ is a prime number, it is $2^{61}+ 1$ that is divisible by three. I apologise if I made a mistake writing the question $\endgroup$ – Ronikos Jan 19 '16 at 22:20
  • 12
    $\begingroup$ If you know that $2^{61}-1$ is prime, $2^{61}+1$ has to be a multiple of 3, since $(a,a+1,a+2)$ must contain a multiple of 3 and the first two can't be (this doesn't address the general case in the question, so it's a comment not an answer) $\endgroup$ – Glen_b Jan 20 '16 at 0:47
  • 1
    $\begingroup$ @Glen_b Just for fun, I wrote out an answer using this sort of observation! $\endgroup$ – Benjamin Dickman Jan 20 '16 at 8:14
  • 1
    $\begingroup$ As hinted at in several answers below, this is exactly the kind of thing that modular arithmetic was invented for. While you can present a solution using "elementary" language, without using (or even being aware of) any terminology from modular arithmetic, that's a bit like driving a nail using a large stone instead of a hammer. Sure, either way works, but having the proper tool makes it so much less awkward. $\endgroup$ – Ilmari Karonen Jan 20 '16 at 13:36
  • 1

11 Answers 11

118
$\begingroup$

Since $2 \equiv -1 \pmod{3}$, therefore $2^{k} \equiv (-1)^k \pmod{3}$. When $k$ is odd this becomes $2^k \equiv -1 \pmod{3}$. Thus $2^k+1 \equiv 0 \pmod{3}$.

$\endgroup$
  • 24
    $\begingroup$ Note that this logic also shows that any even power of two, minus one, is a multiple of 3. $\endgroup$ – Michael Seifert Jan 20 '16 at 19:49
  • 7
    $\begingroup$ I'm suprised such an easy answer got so many votes. $\endgroup$ – N.S.JOHN Apr 17 '16 at 10:18
87
$\begingroup$

A direct alternative to the answer via congruences is to note that for $k$ odd one has the well-known polynomial identity $$ x^{k} + 1 = (x + 1) (x^{k-1} - x^{k-2} + \dots - x + 1), $$ and then substitute $x = 2$.

$\endgroup$
45
$\begingroup$

Another way is by induction:

$$ 2^1+1 = 3 = 3 \cdot 1 $$

Then, if $2^k+1 = 3j, j \in \mathbb{N}$, then

\begin{align} 2^{k+2}+1 & = 4\cdot2^k+1 \\ & = 4(2^k+1)-3 \\ & = 4(3j)-3 \qquad \leftarrow \text{uses induction hypothesis} \\ & = 3(4j-1) \end{align}

$\endgroup$
  • $\begingroup$ Wouldn't it be just easier to prove that if a = b mod m then a^k = b^k mod m by induction then immediately use that fact? $\endgroup$ – djechlin Jan 20 '16 at 0:29
  • $\begingroup$ That proof is super trivial if you assume that a = b mod m implies ax = bx mod m, which you do. tldr, this isn't "another way." $\endgroup$ – djechlin Jan 20 '16 at 0:30
  • $\begingroup$ @djechlin: Fair point. I will rewrite to avoid modular arithmetic altogether. $\endgroup$ – Brian Tung Jan 20 '16 at 4:31
  • 3
    $\begingroup$ +1, but I would have said it a little more simply: $2^{k+2}+1=4\cdot2^k+1=3\cdot2^k\,+\,(2^k+1)$, which is a multiple of 3 iff $2^k+1$ is.  You can also use that to prove that adding 1 to any even power of 2 yields a number that is not a multiple of 3. $\endgroup$ – Scott Jan 20 '16 at 17:20
  • $\begingroup$ This inline notation makes it difficult to see where you've used to hypothesis. Took me way longer to comprehend than it should have for such a simple induction proof $\endgroup$ – Cruncher Jan 20 '16 at 20:29
16
$\begingroup$

One of your examples is that $2^{11} + 1$ is divisible by $3$. We investigate as follows:

Let us consider instead raising $2$ to an even power and subtracting $1$. And then let us factor.

Example: $2^{10} - 1 = (2^5 - 1)(2^5 + 1)$.

Among any three consecutive integers, exactly one of them must be divisible by $3$.

Clearly $2^5$ is not divisible by $3$, so either its predecessor or successor is divisible by $3$.

That is, either $2^5 - 1$ or $2^5 + 1$ is divisible by $3$, whence their product is, as well.

Okay: Their product is $2^{10} - 1$, which we have now established is divisible by $3$.

This number is still divisible by $3$ after being doubled, and still divisible by $3$ when we add $3$ to it.

So: We have that $2(2^{10} - 1) + 3 = 2^{11} - 2 + 3 = 2^{11} + 1$ is divisible by $3$ as desired.

A similar bit of reasoning around $2^{2k} - 1$ yields the assertion at hand. "QED"

$\endgroup$
  • 2
    $\begingroup$ (Just to fill in the last details: Let $k \in \mathbb{Z}$ be arbitrary. Among the three consecutive integers $2^{k} - 1, 2^{k}, 2^{k} + 1$ must be exactly one divisible by three; since $2^{k}$ is not divisible by three, it must be one of the other two, hence their product is divisible by three. This product is $(2^{k} - 1)(2^{k} + 1) = 2^{2k} - 1$; note that multiplying this number by $2$ and then adding $3$ does not affect its divisibility by three, whence $2(2^{2k} - 1) + 3 = 2^{2k+1} + 1$ is divisible by $3$ as desired. QED) $\endgroup$ – Benjamin Dickman Jan 22 '16 at 2:08
11
$\begingroup$

There are only three possibilities for the divisibility of an integer by $3$, which are: no remainder, a remainder of $1$, or a remainder of $2$. But if we multiply $2$ by itself over and over again, the no remainder option is impossible, as that would mean that $2$ is a multiple of $3$, which it is not.

The thing is also that we can multiply reminders. So $2$ leaves a remainder of $2$, and $2 \times 2 = 4$, which leaves a remainder of $1$. And $1 \times 2 = 2$, which leaves a remainder of $2$ again.

Therefore the powers of $2$ alternate remainders on division by $3$ according to the parity of the exponent: $2^n \equiv 1 \pmod 3$ if $n$ is even and $2^n \equiv 2$ or $-1 \pmod 3$ if $n$ is odd.

$\endgroup$
  • 1
    $\begingroup$ Well written for readability by non-mathematicians. Good job. $\endgroup$ – Wildcard Jan 20 '16 at 22:31
  • $\begingroup$ Thank you for the acknowledgement. $\endgroup$ – Mr. Brooks Jan 20 '16 at 22:32
  • 1
    $\begingroup$ A superb answer. $\endgroup$ – Fattie Jan 23 '16 at 12:26
11
$\begingroup$

$2 = 3-1$

$2^k = (3 - 1)^k = 3^k - k*3^{k - 1} ..... = \sum_{n = 0}^k {k \choose n}3^{k - n}(-1)^n = \sum_{n = 0}^{k - 1} {k \choose n}3^{k - n}(-1)^n + {k \choose 3}3^{k - n}(-1)^k = \sum_{n = 0}^{k - 1} {k \choose n}3^{k - n}(-1)^n \pm 1$

Since $k$ is odd:

$2^k = \sum_{n = 0}^{k - 1} {k \choose n}3^{k - n}(-1)^n - 1$

$2^k + 1 = \sum_{n = 0}^{k - 1} {k \choose n}3^{k - n}(-1)^n = 3\sum_{n = 0}^{k - 1} {k \choose n}3^{k - n - 1}(-1)^n$

which is a multiple of 3.

$\endgroup$
9
$\begingroup$

In binary: \begin{align*} 11 &= 11 \cdot 01 \\ 1111 &= 11 \cdot 0101 \\ 111111 &= 11 \cdot 010101 \\ 11111111 &= 11 \cdot 01010101 \\ 1111111111 &= 11 \cdot 0101010101 \\ &~~\vdots \end{align*} Clearly the LHS are of the form $2^{2k}-1$. And we've proved that these are multiples of three by factoring out $11$ in binary! Thus if we double and add three, $$2 \cdot (2^{2k}-1)+3=2^{2k+1}+1$$ is also a multiple of three.

$\endgroup$
8
$\begingroup$

$2^2=4\equiv1\pmod 3$, so $4^k\equiv1\pmod3$ for all integers $k$. And so for any odd number $2k+1$, we get $2^{2k+1}+1 = 4^k\cdot 2+1\equiv 2+1\equiv0\pmod3$.

$\endgroup$
8
$\begingroup$

Using geometric series

Consider $S_k = 1 + 2\sum_{i=0}^{k-1}4^i$. It follows that $S_k$ is in $\mathbb{N}^{+}$. However, $$S_k = 1 + 2\cdot\frac{4^k - 1}{4 - 1} = \frac{2^{2k+1}+1}{3}$$ QED

Using recurrence

For $k\in\mathbb{N}$, consider the recurrence $J_{k+1} = 4J_{k} - 1$, with $J_0 = 1$.

Since $J_0 = 1$, it follows that each of $J_k$ is in $\mathbb{N}^{+}$.

Solving the recurrence yields: $J_k = \frac{1}{3}(2^{2k + 1}+ 1)$.

The characteristic equation $r^2 - 5r + 4 = 0$ follows from $J_{k+2} = 5J_{k+1} - 4J_{k}$.

Hence, $J_k = A\lambda_1^k + B\lambda_2^k$, with $\lambda_1 = 4$ and $\lambda_2 = 1$ as solutions to the characteristic equation.

As $J_0 = 1 \implies J_1 = 3$, it follows that $A = \frac{2}{3}$ and $B = \frac{1}{3}$.

QED

$\endgroup$
6
$\begingroup$

If $k$ is odd, then $2^k$ is $2*2^{k-1}$. If $n$ is not a multiple of 3 then $n^2-1$ is since $n^2-1 = (n-1)(n+1)$ and at least one of them is a multiple of 3. This means that $2*2^{k-1} - 2$ is a multiple of $3$ as is $2*2^{k-1} + 1$.

Hope I helped.

$\endgroup$
  • 1
    $\begingroup$ Welcome to MathSE! See this guide for how to mark up math nicely on this site. $\endgroup$ – Frentos Jan 20 '16 at 14:43
  • $\begingroup$ Thanks! Is the explanation ok? $\endgroup$ – Creator Jan 20 '16 at 14:47
  • $\begingroup$ This looks find. Although it seems basically the same answer as the one posted here. In any case, welcome to the site. $\endgroup$ – Martin Sleziak Jan 20 '16 at 15:03
  • $\begingroup$ It's hard for me to follow - matching up the $n^2=1$ bit with half of $2 * 2^{k-1} - 2$ for instance. And it relies on the assumption that $n$ (which is presumably meant to stand for $2^{(k-1)/2}$?) is not a multiple of 3. $\endgroup$ – Frentos Jan 20 '16 at 15:09
  • $\begingroup$ As far as I know 2 is NOT a multiple of 3 ;). I don't say $n^2=1$ anywhere. $\endgroup$ – Creator Jan 20 '16 at 15:11
1
$\begingroup$

There is exactly one integer that divides three among any three consecutive integers. Since $2^{61}-1$ is prime, $2^{61}$ trivially is not a multiple of $3$, $2^{61}+1$ is a multiple of $3$.

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