Let, $xy=n^{\underline k} = n(n-1)(n-2)\cdot\dotsm\cdot (n-k+1)$ and it is given that $ \gcd(x,y)=1$ with one of $x$, $y$ is odd, another is even. When is $\gcd (x-1,y-1)=z>1$?


In other words, what are necessary (non-trivial) or necessary and sufficient condition(s) on variables $n$, $k$, $x$, $y$ for such cases?


**Examples of trivial cases:**


1. $z \mid (x − 1) +(y − 1) = x+y-2 \implies x+y \equiv2 \pmod z$.
2. A sufficient condition would be that $x−1\mid y−x$.


**A similar-looking problem:**


Let $m$, $n$ be distinct positive integers. Prove that
$\gcd(m, n) + \gcd(m + 1, n + 1) + \gcd(m + 2, n + 2) \le 2\lvert m − n\rvert + 1$.
Further, determine when equality holds (from [34th Indian National Mathematical Olympiad-2019](https://olympiads.hbcse.tifr.res.in/olympiads/wp-content/uploads/2019/02/Inmo-2019-Solutions.pdf)).


*I mentioned the above problem just to show this kind of problem exists, and the problem I posted is not a random problem.*


**A related research result:**


The below result is found in the article entitled ["On the factorization of consecutive integers" by M. A. Bennett, M. Filaseta and O. Trifonov on February 26, 2007](https://www.math.ubc.ca/%7Ebennett/BFTpaper0207.pdf).


Theorem 1.1. If $k \in \{5, 7\}$, $n \ge 2k$ is an integer, and we write
$\binom nk = U \cdot V$,
where $U$ and $V$ are integers where the greatest prime factor $P (U)$ of $U$ is $\le k$ and $V$ is coprime to $k!$, then it
follows that $V > U$, unless
$(n, k) \in \{(10, 5), (12, 5), (21, 7), (28, 5), (30, 7), (54, 7)\} $.


***Note:***


Please consider non-trivial cases.



If $\gcd(x,y)=1$ find necessary and sufficient condition(s) such that $\gcd (x-1,y-1)>1$
This isn't very deep. But it might suggest better results:


I will assume $1 < x <y.$


I will relax the condition on $z$ slightly to $z>1$ and $z\mid \gcd(x-1,y-1).$


It would be enough to solve this for $z$ a prime or prime-power and then combine results.


In addition, I will sometimes ignore the condition $\gcd(x,y)=1$.


When I wrote this I was assuming that $x$ was a factor of one of the $n-i$, for example $z=5$, $x=21$, $k=2$ has solutions


1. $(n-1)n=42\cdot 43=21 \cdot 86$ with $5=\gcd(20,85)$
2. $n(n-1)=273\cdot 272=21\cdot 3536$ with $5=\gcd(20,3535)$
3. $(n-1)n=77\cdot 78=(7 \cdot 11)\cdot(3 \cdot 26)=21\cdot 286$ with $5=\gcd(20,285)$.


I can describe all the cases of type 1 and type 2. But the following does not consider type 3.


I will suggest that for each fixed $k$ the possible $z$ (subject to $x$ being a divisor of one of the $n-i$) can be described and then we can take $x=zt+1>1$ arbitrary and describe exactly which $y$ are then possible. These will be a union of arithmetic progressions. I describe this in any detail only for $k=2$. Larger $k$ should be similar but with more subcases.


Consider first the case $k=2$. There are three cases of which I only consider the first two:


1. $n-1=ax$
2. $n=ax$
3. $n-1=ax\_1$, $n=bx\_2$ with $x\_1,x\_2>1$ and $x=x\_1x\_2$.


In the case 1) of $n-1=ax$ the condition on $z$ turns out to be that $r^2+r-1$ has solutions $\bmod z$. This is equivalent to saying that either $z=\prod\_1^j p \_i^{e\_1}$ or $z=5\prod\_1^j p\_i^{e\_i}$ where each $p\_i \equiv \pm1 \bmod 5$. Then there are $2^j$ solutions $\bmod z$.


We will now see these solutions when $z=5$ are exactly the following when $t\ge 1$, $u \ge 0$. (Note that $r^2+r-1=(r-2)(r-2) \bmod 5$.)


* $z=5$
* $n=(5t+1)(5u+2)+1$
* $x=5t+1$
* $y=\left( 5\,u+2 \right) \left( 25\,tu+10\,t+5\,u+3 \right)$.


To get that $\gcd(x,y)=1$ we must also require $\gcd(u,2t)=1$.


and


The solutions when $z=11$ are exactly the following when $t\ge 1$, $u \ge 0$ and $r=3$ or $r=7$. (Note that $r^2+r-1)=(r-3)(r-7) \bmod 11$.)


* $z=11$
* $n=(11t+1)(11u+r)+1$ for $r=3$ or $r=7$
* $x=11t+1$
* $y=\left( 11\,u+r \right) \left( 11\,rt+121\,tu+r+11\,u+1 \right)$.


To get that $\gcd(x,y)=1$ we must again require $\gcd(u,tr)=1$.


In general:


For


* any $z$ of the form above
* any $x=zt+1>1$ and
* any $a=zu+r$ (for one of the possible values of $r$)


take $n=ax+1=a(zt+1)+1$. Then $$(n-1)n=ax 
 \cdot (ax+1)=(zt+1)\cdot \bigl((zt+1)a^2+a\bigr)=x\cdot y.$$


The extra condition $\gcd(x,y)=1$ is equivalent to $\gcd(zt+1,zu+r)=1$ which is equivalent to $\gcd(u,tr)=1$.


We arranged things so that $z\mid x-1$ and wanted that $z\mid y-1$ as well. That is


$$z \mid a^2(zt+1)+a-1\ \ \ \ \text{i.e.}\ \ \ z\mid(a^2+a-1).$$


But we chose $a$ exactly so that would be true.




---


In the case $n=ax$ we need that $s^2-s-1 \bmod z$ has solutions. The feasible $z$ are the same, and the solutions are exactly $z-r$ where $r$ is a solution for $r^2+r-1=0 \bmod z$.




---


When we go to $k=3$ we need to consider the subcases $n=a(zt+1)+2$, $n=a(zt+1)+1$ and $n=a(zt+1)$. In each case $a$ must satisfy a cubic equation $\bmod z$. These are less elementary. But the concept remains the same.




---


It is a necessary, but not sufficient, condition that all prime divisors of $z$ are greater than $k$, i.e. $\gcd(z,k!)=1$. This is because $k! \mid n^{\underline k}=xy$ and $\gcd(z,xy)=1$.


