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

  • $\begingroup$ Did you encounter an example that seems computationally difficult? $\endgroup$
    – metamorphy
    Jan 2, 2019 at 18:48
  • $\begingroup$ 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$. $\endgroup$
    – Hang Wu
    Jan 3, 2019 at 4:13
  • $\begingroup$ 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. $\endgroup$
    – metamorphy
    Jan 3, 2019 at 7:31
  • $\begingroup$ Funny - for $n=19$ and $a=6$ the resultant appears to be prime, thus the smallest (!!!) solution is $$x=1578270389554680057141787800241971645032008710129107338825798$$ $\endgroup$
    – metamorphy
    Jan 3, 2019 at 7:48

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.