1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that 33 divides 2^55 + 1

  1. Jun 3, 2015 #1
    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. jcsd
  3. Jun 3, 2015 #2

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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.


    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 = 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
  4. Jun 4, 2015 #3
    Brilliant, got it!

    Thanks! =D
     
  5. Jun 4, 2015 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Generalise to ##a^{mn}+1##. Under what circumstances will ##a^n+1## be a factor?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Prove that 33 divides 2^55 + 1
Loading...