Erdős Problem 649: smooth numbers preceding a prescribed prime factor
Statement.
For primes $p<q$, must there exist an integer $n$ whose greatest prime factor is $p$, while the greatest prime factor of $n+1$ is $q$?
Claim and attribution.
No. We give a complete elementary counterexample and then a stronger family using Dirichlet's theorem and quadratic reciprocity. The problem and the congruence obstruction are recorded at
https://www.erdosproblems.com/649. This is a reconstruction of a known disproof.
An explicit counterexample.
Take $p=2$, $q=7$. An integer with greatest prime factor $2$ is $2^a$, $a\geq1$. Its residue modulo $7$ lies in $\{1,2,4\}$, since $2^3\equiv1\pmod7$. Consequently $7\nmid 2^a+1$. In particular the greatest prime factor of $2^a+1$ cannot be $7$. This alone disproves the statement.
Infinitely many obstructions for each fixed $p$.
Let \[
M=8\prod_{\substack{\ell\leq p\\\ell\ {\rm odd\ prime}}}\ell.
\] Dirichlet's theorem supplies infinitely many primes $q\equiv-1\pmod M$; discard the finitely many $q\leq p$. We claim that every prime $\ell\leq p$ is a quadratic residue modulo $q$. For $\ell=2$, this follows from $q\equiv7\pmod8$. For odd $\ell\leq p$, quadratic reciprocity and $q\equiv3\pmod4$ give \[
\left(\frac{\ell}{q}\right)
=(-1)^{(\ell-1)/2}\left(\frac{q}{\ell}\right)
=(-1)^{(\ell-1)/2}\left(\frac{-1}{\ell}\right)=1.
\] Thus every positive integer all of whose prime factors are at most $p$ is a nonzero quadratic residue modulo $q$. But $-1$ is a quadratic nonresidue because $q\equiv3\pmod4$. No such integer can satisfy $n\equiv-1\pmod q$, so $q\nmid n+1$. This proves the stronger obstruction even without requiring that $p$ actually divide $n$.
Scope and dependencies.
The single counterexample uses only modular arithmetic and completely answers the question. Only the supplementary infinite-family statement uses the two classical theorems named above.
Completion estimate.
COMPLETION: 100%