# Find the smallest positive integer $x$ satisfying $\gcd(x^n+a,(x+1)^n+a)>1$

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$$.

• Did you encounter an example that seems computationally difficult? Jan 2, 2019 at 18:48
• For example, $n=19$ and $a=2$. Both $p$ and $q$ are extremely large and cannot be factored easily. I believe the case is quite common for large $n$. Jan 3, 2019 at 4:13
• The procedure I've suggested below gives the resultant as $$1103 \cdot 87211 \cdot 31308253657 \cdot 818790224665362763936013994101920313,$$ and trying $p=1103, 87211, \ldots$ we find $x\bmod p=473, 836, \ldots$ with $473$ the solution. Jan 3, 2019 at 7:31
• Funny - for $n=19$ and $a=6$ the resultant appears to be prime, thus the smallest (!!!) solution is $$x=1578270389554680057141787800241971645032008710129107338825798$$ Jan 3, 2019 at 7:48

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$$).