For every natural number $m$, $2^{2m}-1$ is divisible by $3$

Question

Can anyone tell me if I missed any small details in this proof?

(basis) $2^{2(1)}-1 = 3*1$ which is divisible by 3.

(induction) Fix $m>1$ so $p<m$. Hence for every natural number $p,$ $2^{2p}-1=3p.$ then for every natural number $(p+1),$ $2^{2(p+1)}-1=3(p+1)$ then

$2^{2(p+1)}-1=3(p+1)$

$2*2^{2p}-1=3(p+1)$

$2*2^{2p}-1=3(p+1)$

$2(3p+1)-1=3(p+1)$ by induction hypothesis

$2(3p+1)+2^2-3=3(p+1)$

$6p+3=3(p+1)$

$3(p+1)=3(p+1)$

Thus, the statement is true for the natural number n whenever it is true for any natural number less than n.

Answer 1

Can anyone tell me if I missed any small details in this proof?

Sorry, but your proof is not good at all! You didn't just miss any small details, but your whole proof method is fundamentally wrong. Sorry to be blunt here, but you need to get this proof technique correct.

First, a relatively minor mistake. You state the inductive assumption as: for every natural number $p$: $2^{2p}-1=3p$, and that you are trying to show that $2^{2(p+1)}-1=3(p+1)$

Well, that is just not true. Take $p=2$ then $2^{2p}-1=2^4-1=16-1=15$, but $3p=3\cdot2=6$

Instead, the theorem should be stated as: For any $m$: $2^{2m}-1=3k$ for some integer $k$. So, the inductive hypothesis should be:

$2^{2p}-1=3k$ for some integer $p$ and $k$

and now you need to show that:

$2^{2(p+1)}-1=3k'$ for some integer $k'$

Your second mistake is much more serious though! You start out with what (you think) you are trying to prove:

$2^{2(p+1)}-1=3(p+1)$

and up with a tautology:

$3(p+1) = 3(p+1)$

This is your fundamentally wrong proof strategy, because what you did here proves absolutely nothing at all!

Of course you can derive a tautology from anything at all ... but that does not mean anything as far as what you started with.

Indeed, using your logic, here is a proof that $1=2$:

$1=2$

$0\cdot 1 = 0\cdot 2$

$0=0$

...Correct!?!?!

OK, so that's obviously not the way to prove these. Your mistake is that you start with what you are trying to show. But in a proof, you need to end up with what you are trying to show. Here is what you need to do:

You need to start with the left side:

$2^{2(p+1)}-1$

and see if, using the inductive hypothesis that $2^{2p}-1=3k$, you can rewrite that expression to something of the form $3\cdot (...)$. If you can show that, you can conclude that $2^{2(p+1)}-1 = 3k'$ for some $k'$.

Answer 2

$2^{2m} - 1 = (2^m)^2 - 1 = (2^m - 1)(2^m + 1); \tag 1$

of the three consecutive integers

$2^m - 1, \; 2^m, \; 2^m + 1 \tag 2$

precisely one of the must be divisible by $3$ (this is true of any three consecutive integers); clearly

$3 \not \mid 2^m; \tag 3$

therefore either

$3 \mid 2^m - 1 \; \text{or} \; 3 \mid 2^m + 1, \tag 4$

which implies

$3 \mid (2^m - 1)(2^m + 1) = 2^{2m} - 1. \tag 5$

Doesn't seem to use induction, does it? But to be thorough, we need to prove that $3$ divides precisely one of any three consecutive positive integers . . . and induction might help here! For example, restricting ourselves to the naturals $\Bbb N$, we see that $3$ divides precisely one out of $1, \; 2, \; 3$; now suppose for some $k$, $3$ divides precisely one of $k - 2$, $k - 1$, $k$; now consider the triplet $k - 1$, $k$, $k + 1$; if $3 \not \mid k - 2$, it must by hypothesis divide one of $k - 1$, $k$; but then $3 \not \mid k + 1$, lest it also divide $k - 2 = (k + 1) - 3$, which we have rejected. So $3$ divides exactly one of the triplet $k - 1$, $k$, $k + 1$; and if $3 \mid k - 2$, we have $3 \mid (k - 2) + 3 = k + 1$, so once again $3$ is a factor of precisely one of $k - 1$, $k$, $k + 1$ and our little induction is done.

I find this method a little easier to get my head around, although I commend Bram28's suggestion for a proof, and his explanation, as well.

Note Added in Edit, Thursday 1 November 2018, 6:44 PM PST: OK, so I fooled around with it a little more and found another proof which doesn't invoke the "three consecutive naturals" business, and I think is likely what Bram28 was getting at in his closing sentences; the argument performs induction directly $2^{2k} - 1$; suppose

$3 \mid 2^{2k} - 1; \tag 6$

then

$\exists q \in \Bbb N, \; 2^{2k} - 1 = 3q; \tag 7$

thus,

$2^{2k} = 3q + 1; \tag 8$

now,

$2^{2(k + 1)} = 2^{2k + 2} = 2^{2k}2^2 = 4 \cdot 2^{2k} = 4(3q + 1) = 12q + 4, \tag 9$

whence

$2^{2(k + 1)} - 1 = 12q + 3 = 3(4q + 1), \tag{10}$

and that does it, does it not? $OE\Delta$ End of Note.

Answer 3

With some basis knowdlege with modulo you can do it like this:

$2^{2m}-1\equiv 4^m-1\equiv 1^m-1\equiv 1-1\equiv 0\mod 3$

So $2^{2m}-1$ is divisable by 3.

Answer 4

First the base case:

$$m=1\to 2^{2(1)}-1=3=3\cdot 1$$

so true for $m=1$.

Assume true for $m=k$, that is: $$2^{2k}-1=3t, t\in\Bbb Z$$ Then use this to show for $m=k+1$

I'll leave you two hints to show this:

$$2^{2(k+1)}=4(2^{2k})$$ $$-1=-4+3$$

Answer 5

An option:

$m \ge 1.$

$2^{2m}-1 = (2^2)^m -1=$

$4^m -1= (1+3)^m-1.$

In the binomial expansion of $(1+3)^m$ all terms except the first term have a factor $3$, i.e.

$(1+3)^m=1^m +3k$, where $k \in \mathbb{Z^+}$.

Hence

$2^{2m}-1 = (1^m +3k) -1=3k .$