Greatest prime divisor of consecutive integers

Question

Let $p,q$ be prime numbers with $p<q<2p$. Prove that there exists a pair of consecutive positive integers such that the greatest prime divisor of one of them is $p$ and the greater prime divisor of the other is $q$.

Such a prime number $q$ exists for any $p$ by Bertrand's postulate. For $p=3$ and $q=5$, we can take $5$ and $6$. For $p=5$ and $q=7$, we can take $14$ and $15$. I doubt there exists a general closed form in terms of $p$ and $q$ though.

Answer 1

Bezout's theorem guarantees the existence of integers $m$ and $n$ satisfying

$$pm-qn=1$$

with $0\lt m\lt q$ and $0\lt n\lt p$. (Note, $m$ and $n$ are strictly positive since $p$ and $q$ are distinct primes.) Letting $M=q-m$ and $N=p-n$ we also have

$$qN-pM=1$$

with $0\lt M\lt q$ and $0\lt N\lt p$. Note that $n,N\lt p$ implies $q$ is the largest prime divisor of both $qn$ and $qN$ since $p\lt q$. As for $m$ and $M=q-m$, they can't both be larger than $p$ since that would imply $q=m+M\gt2p$. Thus one of them, at least, is less than or equal to $p$ and hence $p$ is the largest prime divisor of either $pm$ or $pM$ (or both).

As an example, let $p=47$ and $q=89$. We have

$$47\cdot53-89\cdot28=1$$

which is not what we want, since $53$ is a prime larger than $47$, but we also have

$$89\cdot19-47\cdot36=1$$

which does give us what we want.

Remark: It seems likely (or at least plausible) that for "most" pairs $(p,q)$, $p$ is the largest prime divisor of both $pm$ and $pM$. In looking for an example where it isn't, I got lucky: $(47,89)$ was the first pair I thought to try, and it produced $m=53$.

Answer 2

Partial answer:

case 1:

$x = a p$

$x + 1 = b q$

subtract

$1 = b q - a p$

which is solvable for $(a,b)$ when gcd($p$,$q$) = $1$ by the Extended Euclidean Algorithm.

$b < p$ and $a < q$ this can be demonstrated by:

$1 \equiv - a p$ (mod $q$) , $q$ is prime so an $a < q$ exists as an inverse to $-p$.

$1 \equiv b q $ (mod $p$) , similarly $b < p$

Since $b < p < q$ then $q$ is the largest prime factor of $x+1$.

$a < q < 2p$

Can't complete the proof that $p$ is the largest factor of $x$.

---

case 2:

$x = a q$

$x + 1 = b p$

subtract

$1 = b p - a q$

Similarly: $b < q$ and $a < p$

Since $a < p < q$ then $q$ is the largest factor of $x$.

$b < q < 2p$

Can't complete the proof that $p$ is the largest factor of $x+1$.

---

A closed form for $x$:

case 1:

$qx = apq$

$p(x+1) = bpq$

Add or subtract:

$p(x+1) \pm qx \equiv 0$ (mod $pq$)

$x(p \pm q) \equiv -p$ (mod $pq$)

$x \equiv -p(p \pm q)^{-1}$ (mod $pq$)

case 2:

$x \equiv -q(q \pm p)^{-1}$ (mod $pq$)