Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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)$.
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.
Example:
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.)
