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
George C.
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#.

Related questions
Impact of this question
845 views around the world
You can reuse this answer
Creative Commons License