# Prove that 33 divides 2^55 + 1

• jack476
In summary, the conversation discusses a problem from the Mathematical Olympiad Handbook where one needs to prove that 255 + 1 is divisible by 33. The conversation includes relevant equations and the attempt at a solution, which involves factoring polynomials and using long division. However, a simpler solution is presented by pairing terms and generalizing the problem to a^mn + 1, where a^n + 1 is a factor when a^n + 1 = 0 (mod a^mn + 1).
jack476

## Homework Statement

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.[/B]

## Homework 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)

## 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).

jack476 said:

## Homework Statement

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.[/B]

## Homework 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)

## 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).
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:
cnh1995
SammyS said:
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.

Brilliant, got it!

Thanks! =D

jack476 said:
Brilliant, got it!

Thanks! =D
Generalise to ##a^{mn}+1##. Under what circumstances will ##a^n+1## be a factor?

geoffrey159

## What is the statement that needs to be proved?

The statement that needs to be proved is that 33 divides 2^55 + 1.

## What does it mean for a number to divide another number?

A number, say a, divides another number, say b, if there exists an integer, say c, such that b = a*c.

## How can you prove that 33 divides 2^55 + 1?

One way to prove this is by using the concept of modular arithmetic. We can show that 2^55 + 1 is congruent to 0 (mod 33), which means it is divisible by 33. This can be done by finding the remainder when 2^55 + 1 is divided by 33, which should be 0.

## What are the steps involved in proving this statement?

Firstly, we need to express 2^55 + 1 in terms of modular arithmetic. Then, we need to show that it is congruent to 0 (mod 33). This can be done by using the properties of modular arithmetic, such as the rules of exponents and addition. Finally, we need to find the remainder when 2^55 + 1 is divided by 33, which should be 0, proving that 33 divides 2^55 + 1.

## Why is proving this statement important?

Proving this statement is important because it helps us understand the properties and applications of modular arithmetic. It also allows us to solve more complex problems involving divisibility and remainders. Additionally, this statement has applications in number theory and cryptography.

• Precalculus Mathematics Homework Help
Replies
6
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Introductory Physics Homework Help
Replies
21
Views
380
• MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
462
• Precalculus Mathematics Homework Help
Replies
5
Views
1K
• Precalculus Mathematics Homework Help
Replies
11
Views
4K
• Precalculus Mathematics Homework Help
Replies
6
Views
8K
• Calculus and Beyond Homework Help
Replies
7
Views
187
• Calculus and Beyond Homework Help
Replies
11
Views
1K
• Precalculus Mathematics Homework Help
Replies
6
Views
2K