Prove that 33 divides 2^55 + 1

[jack476]

Homework Statement

The problem is exactly as stated in the title: "Prove that 2⁵⁵ + 1 is divisible by 33". This problem is an exercise from the Mathematical Oympiad Handbook in the section on factoring sums of powers.[/B]

Homework Equations

Results found so far in this section:
xⁿ - 1 = (x-1)(x^n-1+ x^n-2 +...+x² +x + 1)

x³ + 1 = (x+1)(x²- x + 1)

x³ + y³ = (x+y)(x²- xy +y²)

The Attempt at a Solution

So far, I have that 33 = 32 + 1 = 2⁵ + 1 = (2+1)(2⁴ - 2³ + 2² -2 + 1) and that 2⁵⁵ + 1 = (2+1)(2⁵⁴-2⁵³+2⁵²+...-2³ + 2² -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).

 

[SammyS]

Homework Statement

The problem is exactly as stated in the title: "Prove that 2⁵⁵ + 1 is divisible by 33". This problem is an exercise from the Mathematical Oympiad Handbook in the section on factoring sums of powers.[/B]

Homework Equations

Results found so far in this section:
xⁿ - 1 = (x-1)(x^n-1+ x^n-2 +...+x² +x + 1)

x³ + 1 = (x+1)(x²- x + 1)

x³ + y³ = (x+y)(x²- xy +y²)

The Attempt at a Solution

So far, I have that 33 = 32 + 1 = 2⁵ + 1 = (2+1)(2⁴ - 2³ + 2² -2 + 1) and that 2⁵⁵ + 1 = (2+1)(2⁵⁴-2⁵³+2⁵²+...-2³ + 2² -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).

In that last expression, look at (2⁵⁴-2⁵³+2⁵²+...-2³ + 2² -2 + 1).

Pair the first two terms 2⁵⁴-2⁵³ = 2(2⁵³) - 2⁵³ = ?

Similarly, pair the next two terms, etc.

Added in Edit:​

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

One of them is as follows:

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

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

 

[jack476]

In that last expression, look at (2⁵⁴-2⁵³+2⁵²+...-2³ + 2² -2 + 1).

Pair the first two terms 2⁵⁴-2⁵³ = 2(2⁵³) - 2⁵³ = ?

Similarly, pair the next two terms, etc.

Added in Edit:​

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

One of them is as follows:

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

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

Brilliant, got it!

Thanks! =D

 

[haruspex]

Brilliant, got it!

Thanks! =D

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