Given positive integers $n$ and $a$, I'd like to ask how to find the smallest positive integer $x$ satisfying $\gcd(x^n+a,(x+1)^n+a)>1$?
I try using the extended Euclidean algorithm on the two polynomials to find the greatest common divisor $\frac{p}{q}$. If $p$ is small, then we just need to check the solutions to $x^n+a \equiv 0 \ (mod \ d)$ where $d$ divides $p$. Otherwise, it seems much harder.
I also notice that $gcd(n,\phi(d))$ should be greater than $1$ in order to have a solution, which helps filter many unfavorable $d$.
I don't quite understand what does $\gcd(y^n+a,(y+1)^n+a)$ give you if it is computed over $\mathbb{Z}[y]$ (if it is roughly what you do; otherwise, probably, we're talking about the same thing).
On the other hand, if $x$ is the solution, $d=\gcd(x^n+a,(x+1)^n+a)$, and $p$ is a prime divisor of $d$, then $x$ is a common root over $\mathbb{Z}/p\mathbb{Z}$ of these two polynomials, and this implies that $p$ divides their resultant, which (up to sign, depending on the definition taken) is equal to $$\det\{r_{i,j} : 1\leqslant i,j\leqslant n\},\qquad r_{i,j}=\begin{cases}-a\binom{n}{j-i},& i < j\\ \hfill\binom{n}{i-j},& i\geqslant j\end{cases}$$ (resembling the "binomial circulant" a.k.a. Wendt's determinant).
Moreover, let $n=p^k m$ with $p\nmid m$. Then, over $\mathbb{Z}/p\mathbb{Z}$, we have $$\gcd(y^n+a,(y+1)^n+a)=g^{p^k}(y),\quad g(y)=\gcd(y^m+a,(y+1)^m+a).$$ As we must clearly have $p\nmid a$, $x$ is a root of $g(y)$, and in fact a simple one (because $y^m+a$ has only simple roots).
This suggests the following idea. For each $p$ found, we solve $g(x)=0$ in $\mathbb{Z}/p\mathbb{Z}$ (I can only suggest general root-finding methods here, such as random splitting), and apply Hensel's lifting to get solutions in $\mathbb{Z}/p^k\mathbb{Z}$ (if needed). If $x$ exists at all, then its value modulo $p^k$ must stabilize eventually (for large enough $k$).