For a fixed $k \geq 2$, are there infinitely many *non-trivial* coprime integer pairs $(x,y)$ for which $xy$ divides $(x+y)^k-1$? By *trivial* I mean parametrized pairs $(x,y)$ of the form $(-1,-1),(x,1),(1,y),(x,1-x),(x,1 - x^n),(1-y^n,y),(x,p(x)),(p(y),y)$, where $p(x)$ is a polynomial factor of $\frac{x^k-1}{x-1}$. When $k$ is even there are a few more trivial pairs, namely $(x,-1),(-1,y),(x,-1-x),(x,x^n-1),(y^n-1,y)$; where $n>0$ is a multiple of $k$.



On the divisibility of $(x+y)^k - 1$ by $xy$
After doing some research online I found out that there's a lot of theory behind this subject and it was studied by several authors (see the references below).


As it was pointed out by @Geoff Robinson, the question essentially reduces to finding all coprime integer pairs $(x,y)$ such that $x \mid 1-y^k$ and $y \mid 1-x^k$.


It turns out that the solutions have a recursive pattern, and this phenomenon was observed by @Aaron Meyerowitz in one of the answers given above. From a single solution one can produce an infinitude of solutions, which form a so-called *1 chain*. A 1 chain is a recursive sequence $u\_n = (1-u\_{n-1}^k)/u\_{n-2}$, with non-zero $u\_0, u\_1$ being given (note that this definition of a 1 chain differs from [4]).


The following construction is a slight variation of Mohanty's argument [4]:


Suppose that $x$ and $y$ are coprime integers which satisfy $x \mid 1-y^k$ and $y \mid 1-x^k$. Then there exists a unique $r \in \mathbb Z$ such that $xr=1-y^k$. But then


$$xr \equiv 1 \pmod{y},$$


$$(xr)^k \equiv 1 \pmod{y},$$


and since $x^k \equiv 1 \pmod{y}$ we have


$$(xr)^k-x^k\equiv 1 - 1 \pmod{y},$$


which results in $x^k(r^k - 1) \equiv 0 \pmod{y}$. Since $\gcd(x,y)=1$, we conclude that $y \mid r^k - 1$. Since $r \mid y^k - 1$, we conclude that $(y,r)$ is also a solution. By proceeding in the same fashion we can generate an infinitude of solutions (see [4] for more details).


Mohanty himself studied a slightly different problem, namely he looked for coprime solutions $(x,y)$ such that $x \mid y^3+1$ and $y \mid x^3 + 1$. One can see that $(x,y)=(1,1)$ is a solution, and the sequence $u\_0=1, u\_1=1, u\_n=(u\_{n-1}^3+1)/u\_{n-2}$ looks as follows:


$$1,1,2,9,365,5403014, \ldots$$


This is a sequence [A003818](https://oeis.org/search?q=1%2C1%2C2%2C9%2C365&sort=&language=&go=Search) in OEIS. According to Benoit Cloitre, this sequence "is asymptotic to $\exp(F\_{2n}\cdot \log c)$ where $F\_n$ is the $n$-th Fibonacci's number and $c\approx1.1137$".


In 1], Bier studies the *polynomial system of congruences* of the form $x \mid g(y)$ and $y \mid f(x)$, where $f(t), g(t) \in \mathbb Z[t]$. He fully classifies for which pairs $(\deg f, \deg g)$ it is possible to have only finitely many solutions. It turns out that there are only finitely many such pairs, and the pairs $(k,k)$ for $k \geq 2$ are not among them.


Any suggestions on how to obtain an asymptotic formula $A(M)$ for the number of solutions satisfying $\max(|x|,|y|)\leq M$ would be greatly appreciated.


References:


1] T. Bier, *Finite or infinite number of solutions of polynomial congruences in two positive integer variables*, Springer Proceedings in Mathematics & Statistics, pp. 11 - 26, 2014.


[2] J. Brzeziński, W. Holsztyński, P. Kurlberg, *On the congruence $ax+by\equiv 1$ modulo $xy$*, Experimental Mathematics 14 (4), pp. 391-401, 2005.


[3] E. Dofs, *Solutions of $x^3+y^3+z^3=nxyz$*, Acta Arithmetica 73 (3), pp. 201 - 213, 1995.


[4] S. P. Mohanty, *A system of cubic Diophantine equations*, Journal of Number Theory 9, pp. 153 - 159, 1977.


[5] L. J. Mordell, *The congruence $ax^3+by^3+c\equiv 0 \pmod{xy}$, and integer solutions of cubic equations in three variables*, Acta Mathematica 88, pp. 77 - 83, 1952.


