What is the GDC(2^32-2^24+2^16-2^8+1, 2^8+1)?

My question is:
GCD(\frac{2^40+1}{2^8+1}, 2^8+1), but I'm stuck here:
GDC(2^32-2^24+2^16-2^8+1, 2^8+1). How I resolve this?

For to get GDC(2^32-2^24+2^16-2^8+1, 2^8+1) I made about the result that
(x^5+y^5) = (x+y)(x^4 - x^3y + x^2y^2-xy^3+y^4) and then, I choose x = 2^8 and y = 1.

1 Answer
Jul 14, 2018

The greatest common divisor of 2^32-2^24+2^16-2^8+1 and 2^8+1 is 1

Explanation:

Note that:

257 = 2^8+1 = 2^(2^3)+1

is a prime number - in fact one of the few known Fermat prime numbers.

So the only possible common factors of 2^8+1 and 2^32-2^24+2^16-2^8+1 are 1 and 257.

However, as you have noted in the question:

2^32-2^24+2^16-2^8+1 = (2^40+1)/(2^8+1)

is of the form:

x^4-x^3y+x^2y^2-xy^3+y^4 = (x^5+y^5)/(x+y)

The one factor (x+y) = 2^8+1 of 2^40+1 corresponds to the real fifth root of unity and (x+y) is not automatically a factor of the remaining quartic x^4-x^3y+x^2y^2-xy^3+y^4 whose other linear factors are all non-real complex.

We can manually divide x^4-x^3y+x^2y^2-xy^3+y^4 by x+y to get a polynomial remainder and then substitute x=2^8 and y=1 to check that this is not a special case...

x^4-x^3y+x^2y^2-xy^3+y^4 = (x+y)(x^3-2x^2y+3xy^2-4y^3)+5y^4

So the remainder is:

5y^4 = 5(color(blue)(1))^4 = 5

Since the remainder is non-zero, 2^32-2^24+2^16-2^8+1 and 2^8+1 have no common factor larger than 1.