What is the greatest constant $c$ such that for any primes $p, q$ with $p<q<cp$, there exist two consecutive positive integers, one with largest prime divisor $p$, and the other with largest prime divisor $q$?

This question shows that $c=2$ works, and the argument uses exactly $c=2$. What can go wrong if $c>2$? For many pairs of primes, it looks like finding such consecutive integers is still possible. For example if $p=3$ and $q=29$, we can take $(144,145)$.


2 Answers 2


For example, $2$ and $23$ won't work. One of the consecutive integers must be a power of $2$. Since the order of $2$ mod $23$ is $11$, $2^k + 1$ is never divisible by $23$, while $2^k - 1$ is divisible by $23$ iff $k$ is divisible by $11$. But then $2^k - 1$ is also divisible by $89$.

EDIT: I suspect that $3$ and $89$ won't work, but I don't have a proof.


For any primes $p, q$ such that $p$ $<$ $q$ $<$ $cp$ will work if and only if for one prime factor $s$ of $q-1$, the largest prime factor of $p^s-1$ is $q$. There are of course other possibilities. To find any two primes $p, q$ choose a prime $p$ and a prime $s$. Now factor $p^s-1$. All factors of $p^s-1$ are congruent to $1$ $\pmod s$, including $q$. Choose the largest prime factor $q$ $|$ $p^s-1$. Now to find constant $c$, divide $q$/$p$, and round up.


Choose $p = 3$, $s = 5$.

$3^5-1$ $=$ $2*11^2$, hence $q$ = $11$, the largest prime factor of $3^5-1$. To find $c$ solve the compound inequality

$3$ $<$ $11$ $<$ $3c$.

$c$ $>$ $11/3$

The smallest integer $c$ would be $c = 4$.

The pair $p$ = $3$, $q$ $=$ $11$, $c$ $=$ $4$ is a solution to your question (If I understood right.)


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .