What is the $GCD(2^{32}-2^{24}+2^{16}-2^8+1, 2^8+1)$?

Question

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

For to get $GCD(2^{32}-2^{24}+2^{16}-2^8+1, 2^8+1)$ I make 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$.

Answer 1

Hint

$$2^8 \equiv -1 \pmod{2^8+1}$$

Therefore $$2^{32}-2^{24}+2^{16}-2^8+1 \equiv (-1)^4-(-1)^3+(-1)^2-(-1)+1 \pmod{2^8+1}$$

Answer 2

$x=2^8$ then $2^{32}-2^{24}+2^{16}-2^8+1=x^4-x^3+x^2-x+1$

Now, let's switch from numbers to polynomials $$x^4-x^3+x^2-x+1 = (x+1)Q(x)+5$$ Where $Q(x)$ is a polynomial with integer coefficients and you can easily see the equality by substituting $x=-1$

From this and Euclidean algorithm: $$ \text{gcd}(\frac{2^{40}+1}{2^8+1}, 2^8+1) = \text{gcd}(5, 2^8+1) = 1$$

Answer 3

\begin{array}{rrrrrrrrrrr} & & & 2^{24} &-2\cdot2^{16} &+3\cdot 2^8 &-4 \\ & &--- &--- &--- &--- &---\\ 2^8+1 &| &2^{32} &-2^{24} &+2^{16} &-2^8 &+1 \\ & &2^{32} &+2^{24} \\ & &--- &---\\ & & &-2\cdot2^{24} & +2^{16} \\ & & &-2\cdot2^{24} &-2\cdot 2^{16} \\ & & &--- &---\\ & & & &3\cdot 2^{16} & -2^8 \\ & & & &3\cdot 2^{16} &+3\cdot 2^8 \\ & & & &--- &---\\ & & & & &-4\cdot 2^8 & +1\\ & & & & &-4\cdot 2^8 & -4\\ & & & & &--- &---\\ & & & & & & +5 \end{array}

\begin{align} \gcd(2^{32}-2^{24}+2^{16}-2^8+1,2^8+1) &= \gcd(2^8+1, 5) \\ &= \gcd(257, 5) \\ &= 1 \end{align}