You are Here: Home >< Maths

# Prove 2^55 + 1 is divisible by 33 watch

1. 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.
2. 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)
3. 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.
4. 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).

http://www.maths.ox.ac.uk/prospectiv...n/lecture1.pdf
5. hey thanks a lot guys.. bit of a delayed reaction from me here but there we are!

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: November 15, 2006
Today on TSR

### University open days

• University of Roehampton
Sat, 17 Nov '18
• Edge Hill University
Faculty of Health and Social Care Undergraduate
Sat, 17 Nov '18
• Bournemouth University
Sat, 17 Nov '18
Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams