# Prove that 33 divides 2^55 + 1

1. Jun 3, 2015

### jack476

1. The problem statement, all variables and given/known data
The problem is exactly as stated in the title: "Prove that 255 + 1 is divisible by 33". This problem is an exercise from the Mathematical Oympiad Handbook in the section on factoring sums of powers.

2. Relevant equations
Results found so far in this section:
xn - 1 = (x-1)(xn-1+ xn-2 +...+x2 +x + 1)

x3 + 1 = (x+1)(x2- x + 1)

x3 + y3 = (x+y)(x2- xy +y2)

3. The attempt at a solution
So far, I have that 33 = 32 + 1 = 25 + 1 = (2+1)(24 - 23 + 22 -2 + 1) and that 255 + 1 = (2+1)(254-253+252+...-23 + 22 -2 + 1)

I do not know how to proceed from here. Presumably I'd want to show that the quotient of the two polynomials is an integer, but I don't know how to do that besides polynomial long division, and I doubt that's what the problem is trying to emphasize (and with so many terms, it would probably take forever, if it's even possible for polynomials of orders 5 and 55- not that I'd want to anyway, with so many terms).

2. Jun 3, 2015

### SammyS

Staff Emeritus
In that last expression, look at (254-253+252+...-23 + 22 -2 + 1).

Pair the first two terms 254-253 = 2(253) - 253 = ?

Similarly, pair the next two terms, etc.

Actually there are some more straight forward ways to do this.

One of them is as follows:

Since you know that 33 = 25 + 1 , You can let x = 25 .

Write 255 + 1 in terms of x . See if you can show that x + 1 divides that result.

Last edited: Jun 3, 2015
3. Jun 4, 2015

### jack476

Brilliant, got it!

Thanks! =D

4. Jun 4, 2015

### haruspex

Generalise to $a^{mn}+1$. Under what circumstances will $a^n+1$ be a factor?