Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
    
@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 – Ronikos Jan 19 at 22:20
12  
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) – Glen_b Jan 20 at 0:47
1  
@Glen_b Just for fun, I wrote out an answer using this sort of observation! – Benjamin Dickman Jan 20 at 8:14
1  
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. – Ilmari Karonen Jan 20 at 13:36
1  

10 Answers 10

up vote 108 down vote accepted

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

share|cite|improve this answer
22  
Note that this logic also shows that any even power of two, minus one, is a multiple of 3. – Michael Seifert Jan 20 at 19:49
2  
I'm suprised such an easy answer got so many votes. – N.S.JOHN Apr 17 at 10:18

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

share|cite|improve this answer

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}

share|cite|improve this answer
    
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? – djechlin Jan 20 at 0:29
    
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." – djechlin Jan 20 at 0:30
    
@djechlin: Fair point. I will rewrite to avoid modular arithmetic altogether. – Brian Tung Jan 20 at 4:31
3  
+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. – Scott Jan 20 at 17:20
    
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 – Cruncher Jan 20 at 20:29

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"

share|cite|improve this answer
2  
(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) – Benjamin Dickman Jan 22 at 2:08

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.

share|cite|improve this answer
1  
Well written for readability by non-mathematicians. Good job. – Wildcard Jan 20 at 22:31
    
Thank you for the acknowledgement. – Mr. Brooks Jan 20 at 22:32
1  
A superb answer. – Joe Blow Jan 23 at 12:26

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

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer
1  
Welcome to MathSE! See this guide for how to mark up math nicely on this site. – Frentos Jan 20 at 14:43
    
Thanks! Is the explanation ok? – Creator Jan 20 at 14:47
    
This looks find. Although it seems basically the same answer as the one posted here. In any case, welcome to the site. – Martin Sleziak Jan 20 at 15:03
    
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. – Frentos Jan 20 at 15:09
    
As far as I know 2 is NOT a multiple of 3 ;). I don't say $n^2=1$ anywhere. – Creator Jan 20 at 15:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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