If $\gcd(x,y)=1$ find necessary and sufficient condition(s) such that $\gcd (x-1,y-1)>1$

Question

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

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.

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.

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