Prove 2^55 + 1 is divisible by 33

Excuse me for being stupid but i'm totally new to this kind of problem and needing some help.. here's what I've done so far...

2^55 + 1

= (2 + 1) (2^54 - 2^53 + 2^52 - ... + 2^4 - 2^3 + 2^2 - 2^1 + 1)

(2^4 - 2^3 + 2^2 - 2^1 + 1) = 11

so 2^55 + 1

= 3(2^54 - 2^53 + 2^52 - ... + 2^5) + 3(11)

= 3(2^54 - 2^53 + 2^52 - ... + 2^5) + 33

and now i'm stuck! and probably barking up the wrong tree.
any help appreciated, thanks.

Reply 1

sebbie

erm, i think this is how you do it....

2^55= (2^5)^11=(32)^11

therefore from fermat's little theorem (32)^11=32(mod 11) so adding one gives 33(mod 11).... which is 0(mod 11)

all odd powers of 2= 2(mod 3) so adding one gives 0 (mod 3)...

this makes 2^55+1= 0(mod 11) + 0(mod 3) = 0 (mod 33)

Reply 2

RichE

Even if you've never met FLT it's ok as the numbers are so small.

Mod 3 and Mod 11 both:-

2^55 + 1 = (2^5)^11 + 1 = 32^11 + 1 = (-1)^11 + 1 = -1 + 1 = 0

As 3 and 11 both divide 2^55+1 then 33 does.

Reply 3

RichE

In answer to a PM of Sebbie on modding numbers - in this specific case we write:-

a = b mod 3 when a-b is a multiple of 3.

It's fairly easy to check that if

a = b mod 3

the

a^n = b^n mod 3 for any natural number n.

So in our example 32 = -1 as the difference is 33 = 3 x 11.

In mod 3 arithmetic there are just three types of number, those of the form

3k, 3k+1, 3k+2.

In mod 11 there are 11 types

11k, 11k+1,... 11k+10.

These are just generalisations of odd and even numbers (which make up mod 2 arithmetic).

There's stuff on the web about this at:-

http://www.maths.ox.ac.uk/prospective-students/undergraduate/sutton/lecture1.pdf

Reply 4

LibLord

hey thanks a lot guys.. bit of a delayed reaction from me here but there we are!