5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ For $p=3$ and $q=q$, we can also take $9$ and $10$. For $p=5$ and $q=7$, we can also take $20$ and $21$. $\endgroup$ Aug 17 '16 at 10:13
  • 1
    $\begingroup$ BTW, I'm pretty sure that for any $p$ and $q$ that you choose, there are exactly $2$ such pairs smaller than $pq$. $\endgroup$ Aug 17 '16 at 10:16
  • 1
    $\begingroup$ @barakmanos, I don't think you always get two pair. See the example in my answer. $\endgroup$ Aug 17 '16 at 14:00
  • $\begingroup$ @BarryCipra: You're right, for $p=47$ and $q=89$ there is only one such pair (namely $1691$ and $1692$). $\endgroup$ Aug 17 '16 at 14:12
5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This is very nice! $\endgroup$ Jun 5 '20 at 22:32
0
$\begingroup$

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

$\endgroup$

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.