What is the GDC(2^32-2^24+2^16-2^8+1, 2^8+1)GDC(232−224+216−28+1,28+1)?
My question is:
GCD(\frac{2^40+1}{2^8+1}, 2^8+1)GCD(240+128+1,28+1) , but I'm stuck here:
GDC(2^32-2^24+2^16-2^8+1, 2^8+1)GDC(232−224+216−28+1,28+1) . How I resolve this?
For to get GDC(2^32-2^24+2^16-2^8+1, 2^8+1)GDC(232−224+216−28+1,28+1) I made about the result that
(x^5+y^5) = (x+y)(x^4 - x^3y + x^2y^2-xy^3+y^4)(x5+y5)=(x+y)(x4−x3y+x2y2−xy3+y4) and then, I choose x = 2^8 x=28 and y = 1y=1 .
My question is:
For to get
1 Answer
The greatest common divisor of
Explanation:
Note that:
257 = 2^8+1 = 2^(2^3)+1257=28+1=223+1
is a prime number - in fact one of the few known Fermat prime numbers.
So the only possible common factors of
However, as you have noted in the question:
2^32-2^24+2^16-2^8+1 = (2^40+1)/(2^8+1)232−224+216−28+1=240+128+1
is of the form:
x^4-x^3y+x^2y^2-xy^3+y^4 = (x^5+y^5)/(x+y)x4−x3y+x2y2−xy3+y4=x5+y5x+y
The one factor
We can manually divide
x^4-x^3y+x^2y^2-xy^3+y^4 = (x+y)(x^3-2x^2y+3xy^2-4y^3)+5y^4x4−x3y+x2y2−xy3+y4=(x+y)(x3−2x2y+3xy2−4y3)+5y4
So the remainder is:
5y^4 = 5(color(blue)(1))^4 = 55y4=5(1)4=5
Since the remainder is non-zero,